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ố:
Code:
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ố