Nguyễn Anh Tôn
(AnhTon)
New Member
Thuật toán:
Input: integer n>1
1. if ( n is the form of 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 the prime)
6. let q be the largest factor of r-1;
7. if (q>= 4 * (r^(1/2)) * log(n)) and (n^((r-1)/q))) mod r <> 1)
8. break;
9. r:=r+1;
10. {
11. for a := 1 to 2*(r^(1/2))*log(n);
12.if ((x-a)^n mod n<>(x^n-a)) and ((x-a)^n mod (x^r -1)<>(x^n-a))output Composite;
13.output Prime;
------------------------------
Tài liệu tham khảo:
1. Báo Toán học và tuổi trẻ số mới nhất ( số 307 tháng 1 năm 2003)
2. Website :
http://www.cse.iitk.ac.in/news/primality.pdf
------------------------------
Em biết sẽ có rất nhiều người ở trên forum Ams biết về thuật toán này. Nhưng em chưa thấy có topic nào bàn luận về thuật toán này cả. Em thấy nó cũng rất hay và có vài chỗ khó hiểu. Hôm nay mới mua báo Toán, chưa có nhiều thời gian để tìm hiểu sâu. Theo như em được biết, thuật toán này tương đối chính xác, chính xác hơn tất cả các thuật toán cỏ điển tìm số nguyên tố. Vì vậy việc tìm hiểu nó có lẽ rất thú vị. Nếu ai đã thử nghiên cứu rồi thì giải thích thuật toán này cho mọi người xem với. Hoặc nếu ai đã thử chuyển thuật toán thành ngôn ngữ lập trình thì càng tốt. Toàn bộ giải thích của 3 nhà nghiên cứu người Ấn Độ cóp trên website về xem khó hiểu quá !
Nếu có thể, xin mọi người giúp đỡ em nha !
--------------------------------
Cho đến bây giờ vấn đề số nguyên tố với loài người vẫn còn nhiều bí ẩn. Liệu với thuật toán này nhân loại có khám phá ra được hết bí mật của số nguyên tố không???
Input: integer n>1
1. if ( n is the form of 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 the prime)
6. let q be the largest factor of r-1;
7. if (q>= 4 * (r^(1/2)) * log(n)) and (n^((r-1)/q))) mod r <> 1)
8. break;
9. r:=r+1;
10. {
11. for a := 1 to 2*(r^(1/2))*log(n);
12.if ((x-a)^n mod n<>(x^n-a)) and ((x-a)^n mod (x^r -1)<>(x^n-a))output Composite;
13.output Prime;
------------------------------
Tài liệu tham khảo:
1. Báo Toán học và tuổi trẻ số mới nhất ( số 307 tháng 1 năm 2003)
2. Website :
http://www.cse.iitk.ac.in/news/primality.pdf
------------------------------
Em biết sẽ có rất nhiều người ở trên forum Ams biết về thuật toán này. Nhưng em chưa thấy có topic nào bàn luận về thuật toán này cả. Em thấy nó cũng rất hay và có vài chỗ khó hiểu. Hôm nay mới mua báo Toán, chưa có nhiều thời gian để tìm hiểu sâu. Theo như em được biết, thuật toán này tương đối chính xác, chính xác hơn tất cả các thuật toán cỏ điển tìm số nguyên tố. Vì vậy việc tìm hiểu nó có lẽ rất thú vị. Nếu ai đã thử nghiên cứu rồi thì giải thích thuật toán này cho mọi người xem với. Hoặc nếu ai đã thử chuyển thuật toán thành ngôn ngữ lập trình thì càng tốt. Toàn bộ giải thích của 3 nhà nghiên cứu người Ấn Độ cóp trên website về xem khó hiểu quá !
Nếu có thể, xin mọi người giúp đỡ em nha !
--------------------------------
Cho đến bây giờ vấn đề số nguyên tố với loài người vẫn còn nhiều bí ẩn. Liệu với thuật toán này nhân loại có khám phá ra được hết bí mật của số nguyên tố không???
