Số nguyên tố | Xét số nguyên tố vô cùng lớn

[huynguyen]

Tháng 8-2002, 1 êkip 3 nhà nghiên cứu Ấn Độ ở Viện công nghệ Kanpur là nhà Tin học Maninda Agrawal và 2 SV Neeraj Kayal, Nitin Saxena, đã hoàn thiện 1 thuật toán, chỉ 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ố:

input: integer n > 1
1. if (n is of the form a^b, 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 (q >= 4 * sqrt(r) * log(n)) and ((n^((r-1)/q) - 1) % r != 0)
8.             break;
9.     r++;
10. }
11. for a=1 to 2 * sqrt(r) * log(n)
12.     if (x - a)^n - x^n + a) % (x^r - 1) != 0 output COMPOSITE;
13. output PRIME

Đây là mã giả, ko phải code đâu nhé
Giải thích:
+ form: dạng
+ composite: hợp số
+ gcd: UCLN
+ prime: nguyên tố
+ factor: ước số

[vinhie47]

Cái này hồi học phổ thông mình có đọc được trên báo TH&TT thì phải :-??

[huynguyen]

Mình cũng mới biết à, vô tình lụm được bí kíp nên share cho bà con đọc chơi ấy mà.

[5primes]

Giải thuật này tuy rất ngắn gọn và được nhiều nhà khoa học trên thế giới quan tâm (cả toán và tin học ) nhưng vẫn chưa được chứng minh tính đúng đắn bằng toán học đâu. Hay bạn nào chứng minh đi vậy

[prog10]

Để ý cái mod ở dòng 12 là mod đa thức nên cũng ko phải dễ ăn của quại.

Thực ra thuật toán này hay ở chỗ với mọi số N thuật toán luôn đạt cỡ O(n^6) với n là số chữ số, chứ nó chay chậm rì giờ người ta dùng elliptic curve (ECPP) kỉ lục là 34093 chữ số.