Thuật toán nguyên tố và đa thức
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (103.81 KB, 2 trang )
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
g(x)=O(f(x)) khi tồn tại một số thực a để luôn có cho mọi x>0). Rõ ràng thời
gian xác định xem liệu n có phải số nguyên tố hay không của thuật toán này là một hàm số
bậc cao hơn hàm đa thức đối với biến log n là (là độ dài biểu diễn số n trong máy tính).
Với thuật toán này, vẫn còn phải mất nhiều thời gian chạy máy mới xác định được một số
tự nhiên cho trước có phải là số nguyên tố hay không.
Một hướng đi khác nhằm giải quyết nhu cầu cấp bách xác định số nguyên tố là các thuật
toán dựa trên cơ sở lý thuyết xác suất. Một loạt các nhà toán học như Rabin 1980,
Goldwasser & Kilian 1986 và Adlermann & Huang 1992…đưa ra các thuật toán mà kết
luận luôn đúng khi khẳng định một số là hợp số, và với một độ bảo đảm được tính trước,
thuật toán có thể khẳng định liệu một số tự nhiên n có phải là số nguyên tố hay không. Như
vậy, với các thuật toán này, máy tính vẫn có thể nhầm lẫn khi khẳng định số 16 là số
nguyên tố với độ bảo đảm là 99%.
Tháng 8 năm 2002, lịch sử chứng kiến một thành công bất ngờ khi nhà tin học Manindra
Agrawal (Viện công nghệ Kanpur ấn độ) cùng với hai sinh viên của mình là Neeja Kayal
và Nitin Saxena đã tìm ra một thuật toán chỉ dài có 13 dòng cho phép xác định chắc chắn
tính nguyên tố của những số rất lớn (có tới hàng trăm chữ số). Việc làm của các nhà tin
học ấn độ là phi thường, vì họ đã thành công khi không biết bao nhiêu người đã cố gắng
mà vẫn thất bại. Chỉ trong một thời gian ngắn, và sau choáng váng ban đầu, các nhà toán
học trên thế giới đã lao vào xem xét kiểm tra sự chính xác của thuật toán và cho tới nay,
vẫn chưa ai phát hiện được sai lầm nào. Tất cả đều thốt lên″Thật là thần diệu, mà sao
không có ai tìm ra được thuật toán này sớm hơn!″
Thuật toán của các nhà tin học ấn độ bắt nguồn từ định lý nhỏ của Fecma mà gần như tất
cả chúng ta đều biết từ nhà trường phổ thông, rằng nếu p là số nguyên tố thì
cho mọi số tự nhiên a.
Định lý này của Fecma được các nhà tin học ấn độ mở rộng cho các đa thức thành một
điều kiện cần và đủ để một số là số nguyên tố mà các bạn sẽ được thấy sau đây trong thuật
toán cụ thể của họ. Chúc các bạn thành công trong việc chuyển thuật toán này thành
chương trình cụ thể và vận dụng vào trong các chương trình của mình
The Algorithm
Input: interger n>1
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;
