PDA

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



huynguyen
02-02-2007, 12:55 AM
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
02-02-2007, 11:41 PM
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
03-02-2007, 12:47 AM
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
29-03-2007, 09:39 AM
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
24-12-2016, 01:01 AM
Để ý 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ì :D giờ người ta dùng elliptic curve (ECPP) kỉ lục là 34093 chữ số.