Thuật toán AKS - Kiểm tra số nguyên tố thời gian đa thức

Trải qua nhiều thế kỷ, con người đã có biết bao nỗ lực tìm kiếm thuật toán hữu hiệu để tìm hiểu số nguyên tố. Bài toán xác định một số có phải là số nguyên tố hay không được xếp vào loại NP - không có thuật toán tất định (một số thuật toán khác như Miller-Rabin là loại thuật toán dựa trên xác suất) trong thời gian đa thức. Cho đến năm 2002, ba nhà khoa học người Ấn Độ là Agrawal, Kayal, Saxena đăng bài báo về thuật toán AKS đưa ra phương pháp kiểm tra số nguyên tố trong thời gian đa thức, đã phá vỡ “lời nguyền“ thiên niên kỷ (khởi đầu từ thuật toán Sàng Eratosthenes ca. 240BC).

Định lý Fermat nhỏ

Đây là định lý làm nền tảng cho thuật toán này. Định lý được phát biểu như sau:

Nếu $p$ là số nguyên tố, và $a$ là một số nguyên không chia hết cho $p$, ta luôn có:

Bạn có thể tìm thấy rất nhiều phương pháp chứng minh định lý thú vị này. Mình xin giới thiệu một phương pháp chứng minh rất đẹp dưới đây.

Chứng Minh

Gọi $S=\{1,2,\dots,p-1\}$ xét tập hợp $aS = \{1a,2a,\dots,(p-1)a\} (\bmod p)$. Nhận xét:

1. Tất cả các phần tử $ai, 1 \le i \le p-1$ không chia hết cho $p$

2. Với $1 \le i,j \le p-1$, nếu $ai \equiv aj (\bmod p)$ mà $\gcd(a,p)=1$ nên $i \equiv j (\bmod p) \implies i=j$

Từ 1 & 2 ta suy ra tất cả các phần tử của $aS (\bmod p)$ là phân biệt nhau, như vậy ta có:

Mở rộng định lý Fermat nhỏ trên đa thức

Đây là mệnh đề tương đương nên ta sẽ phải chứng minh 2 vế.

Vế 1: Nếu $n$ là số nguyên tố thì $(x+a)^n \equiv x^n + a (\mod n)$

Xét:

Vì $n$ là số nguyên tố nên $a^n-a$ chia hết cho $n$. Mặt khác, tất cả các tham số $\displaystyle \binom {n} {k} = \frac {n!}{k! (n-k)!}$ đều là số nguyên nên cũng đều phải chia hết cho $n$.

Vế 2: Nếu $(x+a)^n \equiv x^n + a (\mod n)$với mọi $a,x$ là biến số bất kỳ thì $n$là số nguyên tố.

Ta chứng minh bằng phản chứng. Nếu $n$ là hợp số, gọi $q$ là một thừa số nguyên tố của $n$, và $q^k|n$ ($n$ chia hết cho $q^k$). Xét tham số $\displaystyle \binom n q x^q a^{n-q}$, ta có:

• $\displaystyle \binom n q$không chia hết cho $q^k$vì $n!$trên tử số đã chia cho $q!$ ở mẫu số nên không còn đủ lũy thừa của $q^k$

• $a^{n-q}$ nguyên tố cùng nhau với $q^k$

Vậy tham số của $x^q$ là $\displaystyle \binom n q a^{n-q}$ không chia hết cho $n$ với mọi $a,x$ bất kỳ (trái với giả thiết)

Từ chứng minh của vế 1 & vế 2, ta kết luận định lý trên đúng.

Mấu chốt của thuật toán

Định lý trên làm tiền đề mở ra một phương pháp mới để kiểm tra $n$ có phải số nguyên tố hay không bằng cách chọn một giá trị $a$ và thay vào định lý trên để kiểm tra có thỏa điều kiện không. Tuy nhiên, để tính được $(x+a)^n$, ta vẫn phải tính các hệ số của đa thức khi khai triển ra và vì thế chúng ta vẫn phải tính $n+1$ lần làm cho độ phức tạp thuật toán vẫn không giảm. Tuy nhiên ta có thể hạ bậc của $(x+a)^n \equiv x^n+a$ bằng cách đem cả hai vế chia lấy phần dư cho đa thức $x^r - 1$, với một gía trị $r$ được chọn đủ nhỏ, đa thức phần dư sẽ có bậc nhỏ hơn $r$ và làm giảm độ phức tạp thuật toán.

Tính nhanh $(x+a)^n \bmod x^r -1$

Để ý rằng, để tính $(x+a)^n \bmod (x^r-1)$, chúng ta có thể áp dụng phương pháp liên tục bình phương và chia lấy phần dư để tiết kiệm tính toán thay vì phải tính $n+1$hệ số rồi mới đem chia.

Ví dụ:

Nghĩa là, thay vì dạng gốc, ta sẽ kiểm tra dạng rút gọn như dưới đây:

Tiếp tục, tính nhanh $x^n+a \bmod x^r-1$

Biểu thức trên có thể tính dễ dàng trong $O(1)$ như sau:

Ví dụ: $x^5+3 \bmod x^3 - 1 = x^2+3$, và $x^4 + 2 \bmod x^2-1 = 3$.

Bạn có thể tự chứng minh điều này dễ dàng.

Đây là ý tưởng chính và là điểm mấu chốt của thuật toán AKS. Kể từ phần sau phần này, mình sẽ chỉ đưa ra tóm tắt ý tưởng mà không chứng minh vì trong bài báo gốc đã chứng minh khá ổn, các bạn đọc đến đây, có thể tự tham khảo lại từ bài báo gốc.

Định lý AKS (định lý chính)

Bây giờ vấn đề đặt ra là, có $n$ là hợp số và vẫn thỏa mãn điều kiện (**): $(x+a)^n \equiv x^n + a (x^r-1, \bmod n)$nhưng lại không thỏa (*): $(x+a)^n \equiv x^n + a (\bmod n)$. May mắn thay, vấn đề này được giải quyết thông qua định lý AKS, phát biểu lại từ thuật toán:

Cho giá trị $r$ nguyên tố cùng nhau với $n$ sao cho $o_r(n) \gt \log^2n$, với $o_r(n)$ là cấp của nhóm nhân $(\mathbb Z / r \mathbb Z)^{\times}$( hay nói cách khác, các phần tử $n^i \bmod r,$với $1 \le i \le \log^2 n$ phân biệt nhau). Giả sử với mọi giá trị $1\le a \le O(r\log n)$đều thỏa mãn tính chất $(x+a)^n \equiv x^n + a (x^r - 1,\bmod n)$, và $\gcd (a,n)=1$thì $n$ hoặc là một số nguyên tố, hoặc là một lũy thừa của một số nguyên tố.

Sự tồn tại của giá trị $r$

Từ đầu đến giờ, chúng ta đã đi thông qua các ý tưởng sau:

• Dùng định lý Fermat nhỏ mở rộng để biến bài toán thành dạng đa thức

• Giảm bậc của đa thức gốc bằng cách modulo cho $x^r-1$

• Chứng minh rằng với một số giá trị của $r$ và $1\le a \le O(r\log n)$ thỏa mãn (**), thì sẽ là số nguyên tố hoặc lũy thừa của một số nguyên tố.

Nghĩa là, ta sẽ xét tất cả các giá trị $a$ trong khoảng $1\le a \le O(r\log n)$ để kiểm tra $n$ có phải số nguyên tố hay không. Điều cuối cùng, ta cần chứng minh là tồn tại một giá trị $r$ tốt, phù hợp để làm cho độ phức tạp bài toán thành đa thức với bổ đề chứng minh về sự tồn tại của $r$:

Tồn tại $r=O(\log n)$, và $\gcd (r,n) = 1$ sao cho $o_r(n) \gt \log^2n$, với $o_r(n)$là cấp của nhóm nhân $(\mathbb Z / r \mathbb Z)^{\times}$.

Demo

Lời bàn

Đây là chi tiết về các bước của thuật toán trong bài báo:

Thuật toán AKS có độ phức tạp khoảng $O(r^{3/2}(\log n)^3)$ với chi tiết như sau:

• Kiểm tra $n$ có phải là một lũy thừa cần $O((\log n)^3)$

• Tìm kiếm $r$ thỏa $o_r(n) \gt (\log n)^2$ cần $O(r(\log n)^2)$

• Kiểm tra $\gcd (a,n) > 1$cho các giá trị $a \le r$ cần $O(r(\log n)^2)$

• Kiểm tra $(x+a)^n \equiv x^n + a (\bmod n, x^r - 1)$cho $a=1,2,\dots [\sqrt r \log n]$, mỗi bước cần $O(r^{3/2}(\log n)^3)$

Tóm lại, thuật toán bị ảnh hưởng lớn bởi cách chọn $r$, tuy nhiên có một giới hạn là $r>(\log n)^2$, điều này có nghĩa là thuật toán có giới hạn chặn dưới là $O((\log n)^6)$… Một con số khá ấn tượng, tuy rằng vẫn chưa thể so sánh với Miller-Rabin, nhưng dù sao cũng là cơ sở để chúng ta hy vọng về một phương pháp xuất sắc hơn trong tương lai.