Tiểu Luận Các thuật toán số học cơ bản và bài toán nhận biết số nguyên tố

0. Lời nói đầu Từ những năm 70, sự phát triển của nền Tin học Số học nói riêng đã có những tác động quan trọng đến nhiều mặt của đời sống, trong đó có thể kể đến các lĩnh vực xử lý thông tin, mật mã và kỹ thuật máy tính. Sự phát triển song song này mở ra một hướng đi mới khi nghiên cứu về số học, đó chính là số học thuật toán. Báo cáo xin phép được trình bày sơ qua về một vài thuật toán số học cơ bản, và đi sâu hơn vào các thuật toán nhận biết số nguyên tố, cùng những phân tích, đánh giá sẽ được nói đến cụ thể ở từng phần.
Dù đã rất cố gắng tìm hiểu, song báo cáo này chắc chắn không thể tránh khỏi những sai sót, khiếm khuyết cả về mặt nỗi dung lẫn vấn đề trình bày. Rất mong nhận được những góp ý quý giá của thầy để báo cáo được hoàn thiện hơn. Em xin cảm ơn thầy!

1. Định nghĩa Thuật toán
Thuật toán là một (hoặc một tập hợp) quy tắc, thao tác để với dữ liệu đầu vào đã cho, ta tìm được lời giải sau một khoảng thời gian hữu hạn.


Về cơ bản, thuật toán cần thỏa mãn 2 yêu cầu sau:

Tính xác định: Tại mỗi bước, các thao tác phải được xác định cụ thể, hay nói cách khác là phải chỉ rõ được việc cần làm.
Tính hữu hạn: Thuật toán phải kết thúc sau một khoảng thời gian hữu hạn. Khi thuật toán kết thúc, ta phải thu được lời giải cho vấn đề được đưa ra.