Chủ đề này có 12 trả lời

[canh_dieu]

Cái này xảy ra lâu rồi, hình như chưa ai post lên. Mong được các cao thủ về lý thuyết độ phức tạp thuật toán (?) cho lời bình luận.

Tháng 8 năm 2002 chứng kiến một sự kiện chấn động trong cộng đồng các nhà lý thuyết số và khoa học máy tính: Tiến sĩ Manindra Agrawal cùng 2 học trò của mình là Neeraj Kayal và Nitin Saxena tại Viện công nghệ Ấn Độ (IIT) đưa ra một thuật toán giúp xác định xem một số tự nhiên cho trước có phải là nguyên tố hay không với thời gian đa thức, do đó giải quyết trọn ven bài toán tồn tại khá lâu mà các nhà khoa học máy tính đặt tên là http://dientuvietnam...etex.cgi?log_2n vì trong hệ nhị phân http://dientuvietnam...n/mimetex.cgi?n được biểu diễn bởi http://dientuvietnam...ex.cgi?1 log_2n kí tự (Thấy nói vậy, không biết đúng không ).

Từ lâu người ta đã biết đến bài toán sau, coi như là một mở rộng của Định lí nhỏ Fermat:

Bài toán. Cho http://dientuvietnam...n/mimetex.cgi?a và http://dientuvietnam...n/mimetex.cgi?n là 2 số nguyên dương, http://dientuvietnam...n/mimetex.cgi?n là số nguyên tố khi và chỉ khi http://dientuvietnam.../mimetex.cgi?n.

Tuy vậy, tiêu chuẩn này không thể được dùng để kiểm tra tính nguyên tố của http://dientuvietnam...n/mimetex.cgi?n vì sẽ phải kiểm tra cả thảy http://dientuvietnam...n/mimetex.cgi?n hệ số của biểu thức http://dientuvietnam...imetex.cgi?(x a)^n-(x^n+a), do đó thời gian thực hiện không thể là đa thức của http://dientuvietnam.net/cgi-bin/mimetex.cgi?log_2n đuợc.

Ý tưởng của các tác giả là tìm một tiêu chuẩn tương tự như trên cho một đa thức bậc http://dientuvietnam.net/cgi-bin/mimetex.cgi?s, với http://dientuvietnam.net/cgi-bin/mimetex.cgi?s chặn trên bởi đa thức của http://dientuvietnam.net/cgi-bin/mimetex.cgi?log_2n. Khi đó việc kiểm tra tiêu chuẩn này chỉ cần khoảng http://dientuvietnam.net/cgi-bin/mimetex.cgi?s bước thực hiện.

Và đây là thuật toán AKS (lấy theo chữ cái đầu của tên 3 tác giả này). Kí hiệu http://dientuvietnam.net/cgi-bin/mimetex.cgi?ord_s(n) là số http://dientuvietnam.net/cgi-bin/mimetex.cgi?i nhỏ nhất sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?s, http://dientuvietnam.net/cgi-bin/mimetex.cgi?\phi là hàm Euler.

INPUT: một số nguyên dương http://dientuvietnam.net/cgi-bin/mimetex.cgi?n>1

1. Nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?s nhỏ nhất sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?1<(a,n)<n với http://dientuvietnam.net/cgi-bin/mimetex.cgi?a chạy từ 1 đến http://dientuvietnam.net/cgi-bin/mimetex.cgi?&#091;2\sqrt{\phi(s)}log_2n], nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?n thực sự là số nguyên tố thì thuật toán không thể dừng ở các bước 1,3,5. Với các nhà khoa học máy tính thì không khó khăn lắm để chỉ ra một thuật toán cho bước 1 với thời gian đa thức. Ở bước 2, các tác giả đã chứng minh được rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?n, trong đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?P_s(x) là đa thức dư của phép chia http://dientuvietnam.net/cgi-bin/mimetex.cgi?(x+a)^n-(x^n+a) cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?x^s-1. Hiển nhiên http://dientuvietnam.net/cgi-bin/mimetex.cgi?P_s(x) có bậc không quá http://dientuvietnam.net/cgi-bin/mimetex.cgi?s (và tất nhiên phụ thuộc vào http://dientuvietnam.net/cgi-bin/mimetex.cgi?a, nhưng không quan trọng). Đó chính là điều mà ta mong muôn ở trên. Vấn đề thời gian đa thức do đó đã được giả quyết, câu hỏi còn lại là tính đúng đắn của các bước 4, 6, tức là, liệu có thể nào thuật toán in ra NGUYÊN TỐ, khi input là hợp số được không. Việc kiểm tra điều đó với bước 4 không khó lắm. Khó khăn của vấn đề nằm ở bước 6. Để chỉ ra tính đúng đắn của nó, ta phải chứng minh rằng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?s,n của bước 5, nếu với mọi http://dientuvietnam.net/cgi-bin/mimetex.cgi?n bắt buộc phải là số nguyên tố: một mệnh đề tương tự với bài toán ở trên. Chứng minh định lí này là công việc chủ yếu của các tác giả trên trong bài báo của họ.




Ghi chú:

1. Các bạn có thể xem thông tin về sự kiện này tại http://www.ams.org/n...a-bornemann.pdf

2. Bài báo của 3 tác giả trên http://www.cse.iitk....rimality_v3.pdf

3. Tác giả của cái link đầu tiên nói rằng Neeraj Kayal và Nitin Saxena là thành viên thi IMO của Ấn Độ năm 1997 (tức cùng thời với Đỗ Quốc Anh nhà ta). Nhưng tớ tra trên mạng không thấy, có sự nhầm lẫn nào chăng?

4. Nhờ công trình này và các kết quả khác, Tiến sĩ Manindra Agrawal đã được trao giải của Viện Toán Clay, 2002.

3. Công trình này ra đời đã được 3 năm, nhưng tớ không biết nó đã được đăng trên tạp chí nào. Có ai biết số phận của nó ra sao rồi không?

[RongChoi]

Công trình này theo RC biết là chưa được đăng nhưng sẽ được đăng trên Annals of Maths.

Công trình này có ý nghĩa lớn về mặt lý thuyết vì chứng tỏ được rằng bài toán mở Primality nằm trong lớp các bài toán P (lớp các bài toán giải được trong tgian đa thức trên máy Turing đơn định)

Về mặt thưc tế, công trình này không có ý nghĩa là bao. Độ phức tạp cao (mũ 6 trên độ dài biểu diễn dữ liệu). Trong thực tế, để sinh số nguyên tố lớn, người ta kết hợp hai loại thuật toán xác suất: Thuật toán kiểu Monte-Carlo (nếu trả lời là "nguyên tố" thì 99% đúng chẳng hạn) và kiểm thử lại những số tìm được bằng thuật toán kiểu Las-Vegas : nếu thuật toán dừng và cho kết quả "số nguyên tố" thì đó đúng 100% là số nguyên tố, nhưng nếu xác suất thuật dừng trong khoảng thời gian "hữu hạn" là 99% chẳng hạn. Do đó với đầu vào là 99% là số nguyên tố, sau thuật toán kiểu Las Vegas, sẽ có xác suất 99%*99% là tìm được số 100% nguyên tố. Ví dụ về thuật toán Primality kiểu Monte-Carlo là Miller-Rabin, kiểu Las Vegas là Goldwasser et al. Do độ phức tạp các thuật toán này nhỏ hơn nhiều so với AKS nên trong thực tế người ta ko áp dụng AKS.

[nemo]

Từ lâu người ta đã biết đến bài toán sau, coi như là một mở rộng của Định lí nhỏ Fermat:

Bài toán. Cho http://dientuvietnam...n/mimetex.cgi?a và http://dientuvietnam...n/mimetex.cgi?n là 2 số nguyên dương, http://dientuvietnam...n/mimetex.cgi?n là số nguyên tố khi và chỉ khi http://dientuvietnam.../mimetex.cgi?n.

Thực tế vẫn có những hợp số thỏa mãn phương trình đồng dư trên với các giá trị đặc biệt của x và a, người ta gọi là những số "giả nguyên tố" (Số Carmichael thì phải), số bé nhất là 561 !

[RongChoi]

Thực tế vẫn có những hợp số thỏa mãn phương trình đồng dư trên với các giá trị đặc biệt của x và a, người ta gọi là những số "giả nguyên tố" (Số Carmichael thì phải), số bé nhất là 561 !

Anh nghĩ ý của canh_dieu là xét (x+a)^n và x^n+a như những phần tử của vành Z_n[x].

Còn số Carmichael là những số n để tập các số a thỏa mã a^{n-1} = 1 (mod n) bằng tập Z*_n.

[Polytopie]

Có cái ký hiệu ( ,n)=1 có lẽ phải ghi là gcd( ,n) mới đúng chứ nhỉ?


----------------


Cái bọn Annals of Maths lắm chuyện thật. Bài này đã đưa ra 3 năm rồi mà giờ mới định đăng lên.

[canh_dieu]

@Rongchoi: 1. Tớ cũng biết là các tác giả bài báo này muốn được đăng ở Annals of Mathematics, nhưng không biết đã được chấp nhận chưa. Theo như Rongchoi viết thì đã được chấp nhận rồi?

2. Chắc nemo không có ý định tranh cãi về bài toán đó đâu, vì chắc ai cũng hiểu đó là đồng dư của đa thức, mặc dú tớ đã không nói rõ ra . Có lẽ nemo chỉ muốn đưa thêm thông tin.

@ Polytopie: 1. Cả 2 kí hiệu đó đều không sai

2. Bọn Annals of Mathematics nếu không chịu đăng thì có lẽ là do (cách viết) bài báo đó của mấy bác này sặc mùi Khoa học máy tính hơn là Toán

Bài viết đã được chỉnh sửa nội dung bởi canh_dieu: 01-03-2005 - 07:33

[RongChoi]

@Rongchoi: 1. Tớ cũng biết là các tác giả bài báo này muốn được đăng ở Annals of Mathematics, nhưng không biết đã được chấp nhận chưa. Theo như Rongchoi viết thì đã được chấp nhận rồi?

Annals of Mathematics, 160 (2004), pages 781-793

Chi tiet tai: http://www.math.prin...2004/160_2.html

[JCuteVampire]

Hix hix, tới h tui còn chưa thông 1 chỗ, mong các pác chỉ giùm:
_ Làm thế nào để biết được n có phải là dạng a^{b} hay không?

[canh_dieu]

Làm thế nào để biết được n có phải là dạng a^{b} hay không?

Tớ nghe vu vơ ở đâu đó rằng có thể dùng thuật toán tương tự như Thuật toán lặp Newton để trả lời cho câu hỏi của bạn. Tìm kiếm trên Google với các từ khóa " perfect-power + Newton iteration " có ra một đống đấy. Nhưng tớ không biết tí gì về mấy cái trò này nên chịu. Bạn thử xem sao.

Nếu vẫn không được thì đành đợi các cao thủ trong diễn đàn ra tay vậy.

[nemo]

Vậy phải chăng độ phức tạp của giải thuật kiểm tra n có dạng lũy thừa đơn giản hơn giải thuật kiểm tra n có chia hết cho một số k nào đó không trong một vài trường hợp đặc biệt của n rất lớn !?

[RongChoi]

Thuật toán kiểm tra xem n có dạng d^{e} hay không thực ra là rất đơn giản, và có thể thực hiện trong thời gian đa thức.
Khi nói thuật toán có thể thực hiện trong tgian đa thức, tức là ta hiểu tổng thời gian thực hiện thuật toán là một đa thức theo độ dài biểu diễn dữ liệu đàu vào. Với k bít, ta có thể biểu diễn tất cả các số từ 00..00 đến 11..11 (đọ dài k bít), tức là từ 0 cho tới 2^{k}-1 theo hệ thập phân. Do vậy với đầu vào là n, ta cần k = log(n) bít để biểu diễn n. Nói cách khác, k thỏa mãn 2^{k-1} < n < 2^{k} – 1. Ta sẽ phải lập một thuật toán với thời gian tính toán là đa thức theo k.

Đầu tiên thấy ngay, vì d>= 2 nên e<=k. Do vậy ta sẽ thử với từng e từ 2 đến k. Với mỗi e ta sẽ thây rằng số các d cần thử sẽ là đa thức của k.

Thật vậy : 2^{k-1} < n = d^{e} < 2^{k} – 1 nên 2^{k-1/e} < d <= 2^{k/e}.
Mục đích của ta là tìm (nếu có) số w trong khoảng từ u = 2^{k-1/e} đến v = 2^{k/e} để w^{e} = n (tức khi đó d = w).
Thuật toán tìm kiếm có thời gian chỉ là log(v-u) <= log(n) <=k phép so sánh. Mỗi phép so sánh là một phép thử liệu w^{e} có bằng n hay không. Như vậy thực chất mỗi phép so sánh là một phép tính w^{e}.
Để tính w^{e} chỉ cần log(e) phép nhân.
Phép nhân giữa 2 số a và b thì chỉ cần log(b) phép dịch bít hoặc cộng 1 đơn vi. Dịch bít và cộng 1 là các phép cơ sở và có thể coi thời gian tính toán la 1 đơn vi.

Tổng hợp các tính toán kể trên thì tgian tổng cộng dễ thấy là đa thức. Kết quả chính xác là O(k^{3}log(k)) = O(log^{3}(n)*log(log(n)).

[Joketery]

có ai có thể chuyển cái thuật toán đó về dạng ngôn ngữ lập trình ko (pascal,VB,ASP... chẳng hạn) em mới học cấp 2 thôi nên đọc mấy cái nì chẳng hiểu gì cả, với lại em cũng đang kiếm 1 cái hàm kiểm tra số nguyên tố (cách cũ: xét mod của x từ 2 tới (x/2) quá chậm)

[Alligator]