Thuật toán AKS notes
Đị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ó:
$$a^p \equiv p (\bmod p)$$
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.
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:
Tất cả các phần tử \(ai, 1 \le i \le p-1\) không chia hết cho $p$
Với \(1 \le i,j \le p-1\), nếu: \(ai \equiv aj (\bmod p)\), mà \((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, như vậy ta có:
$$\begin{align*} aS (\bmod p) &= \{1,2,\dots,p-1\} \\ \iff \prod_{i=1}^{p-1}ia = 1a\times 2a \times \dots \times (p-1)a &\equiv 1 \times 2 \times \dots \times (p-1) (\bmod p) \\ \iff a^{p-1} &\equiv 1 (\bmod p) \\ \iff a^p &\equiv a (\bmod p) \end{align*}$$
Định lý Fermat nhỏ mở rộng trên đa thức
$$\begin{align*} &\text{Let } a \in \mathbb Z, n \in \mathbb N, n \ge 2, (a,n)=1 \text{ then} \\ &(x+a)^n \equiv x^n + a (\mod n) \text{ if and only if } n \text{ is a prime number} \end{align*}$$
Đâ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:
$$\begin{align*} (x+a)^n - (x^n + a) &= x^n + \binom{n}{1}x^{n-1}a + \binom{n}{2}x^{n-2}a^2 + \dots + \binom{n}{n-1}xa^{n-1} + a^n - (x^n + a) \\ &=\binom{n}{1}x^{n-1}a + \binom{n}{2}x^{n-2}a^2 + \dots + \binom{n}{n-1}xa^{n-1} + (a^n - a) \\ &= \sum_{i=1}^{n-1} \binom n i x^{n-i}a^i + (a^n - a) \end{align*}$$
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ố \(\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ố \(\binom n q x^q a^{n-q}\), ta có:
\(\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à \(\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.
Ý tưởng chính 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 số $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 \(n+1\) tham số của nó và vẫn làm cho độ phức tạp thuật toán vẫn là $O(n)$. 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\) tham số rồi mới đem chia.
Ví dụ:
$$\begin{align*} (x+1)^5 \bmod (x^2-1) &= (x+1)(x+1)^4 \bmod (x^2-1) \\ &= (\underbrace{(x+1) \bmod (x^2-1)}{x+1})(\underbrace{((x+1)^2)^2}{(x+1)^4} \bmod (x^2-1)) \\ &=(x+1)(\underbrace{(x+1)^2 \bmod (x^2-1)}{2x+2})^2 \\ &=(x+1)(\underbrace{(2x+2)^2 \bmod (x^2-1)}{8x+8}) \\ &=(x+1)(8x+8) \bmod (x^2-1) = 16x+6 \end{align*}$$
Nghĩa là, thay vì dạng gốc, ta sẽ kiểm tra dạng rút gọn như dưới đây:
$$\boxed{(x+a)^n \equiv x^n + a (x^r - 1,\bmod n)} (**)$$
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:
$$x^n+a \bmod x^r-1 = \begin{cases} a+1, \quad \text{ if } r|n \\ x^{n \bmod r} + a, \quad \text{ otherwise} \end{cases}$$
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ể dễ dàng tự chứng minh điều này.
Đị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à \((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ì $n$ 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à \((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.