Thuật toán xác định số nguyên tố với thời gian đa thức - Một sự kiện lớn
trong lịch toán tin của nhân loại
Vũ Đình Hoá
Xác định số nguyên tố là một bài toán cơ bản của toán học và ý nghĩa của bài toán này
càng được tăng lên trong thời đại máy tính điện tử. Từ những năm 1801, ông vua số học
Gauss đã tiên đoán được điều này khi viết ″Vấn đề phân biệt số nguyên tố với hợp số và
phân tích hợp số thành tích các số nguyên tố được biết là một trong những bài toán quan
trọng và có ích nhất của số học…″. Điều nằy đặc biệt đúng khi số nguyên tố chính là cơ sở
của mật mã khóa công khai, cơ sở toán của lý thuyết bảo mật thông tin trên mạng và
thương mại điện tử…của thời đại hiện nay.
Từ những năm trước công nguyên, các nhà toán học đã cố gắng tìm cách xác định số
nguyên tố. Quãng 240 năm trước Công nguyên, loài người đã biết đến sàng Eratosthene để
xác định số nguyên tố. Nhưng sàng này làm việc không hiệu quả. Việc xác định một số
nguyên tố lớn rất khó khăn và mất nhiều thời gian. Chính vì vậy, các nhà toán học vẫn theo
đuổi mục tiêu tìm cách xác định số nguyên tố một cách nhanh chóng và có hiệu quả.
Sau nhiều năm tìm kiếm không hiệu quả, năm 1976, nhà toán học Miller đã đưa ra một
thuật toán thỏa mãn được những yêu cầu nói trên của nhân loại. Nhưng điều khó chấp nhận
trong thuật toán Miller là ông ta không chứng minh được tính đứng đắn của thuật toán
mình đưa ra, mặc dù thuật toán chạy rất tốt và luôn xác định đúng số nguyên tố. Nếu giả
thuyết còn chưa chứng minh được của nhà toán học Riman người Đức (1826-1866) rằng
tất cả các zero ảo của hàm dzêta

có một phần ảo là 1/2 (đây là một trong các
bài toán lớn chưa giải được của nhân loại) là đúng, thì người ta chứng minh được sự đúng
đắn của thuật toán của Miller là nó luôn cho ta các số nguyên tố. Như vậy, việc chứng tỏ
sự đúng đắn của thuật toán Miller là chưa có thể trong thời đại hiện nay.
Các năm tiếp theo, Adlerman, Pomerance và Rumely (1983) đưa ra một thuật toán xác
định xem một số tự nhiên n cho trước có phải là số nguyên tố hay không và với một lượng
thời gian chạy máy là

(ở đây ta ký hiệu logn là và quy ước là ta viết

1. if (n is of the form

, b>1) output COMPOSITE;
2. r=2;
3. while (r<N){
4. if (gcd(n,r) 1) output COMPOSITE;
5. if (r is prime)
6. let q be the largest prime factor of r-1;
7. if (

)and (

)
8. break;
9. }
11. for a=1 to

12. if
output COMPOSITE;
13. output PRIME;