14.3K 216 1.7K

Đã đăng vào Thứ Sáu, 2:16 SA 10 phút đọc

Cấu trúc dữ liệu và Giải thuật Bài 151: Thuật toán Kiểm tra Số nguyên tố Đa thức AKS (Agrawal-Kayal-Saxena Primality Test) - Cột mốc lịch sử chứng minh PRIMES is in P hoàn toàn tất định và không phụ thuộc vào giả thuyết Riemann.

Trong lý thuyết độ phức tạp tính toán và lý thuyết số, câu hỏi: "Liệu việc xác định một số nguyên có phải là số nguyên tố hay không có thể thực hiện được trong thời gian đa thức?" từng là một trong những bài toán mở lâu đời và quan trọng nhất.

Trước năm 2002, mọi thuật toán kiểm tra số nguyên tố đều phải đánh đổi ít nhất một trong bốn tiêu chí cốt tử:

Thuật toán Fermat / Miller-Rabin / Solovay-Strassen: Chạy trong thời gian đa thức rất nhanh ( $O(k \log^3 n)$ ), nhưng mang tính ngẫu nhiên hóa (Randomized / Probabilistic) — luôn tồn tại một xác suất sai số dù nhỏ (thuộc lớp BPP / co-RP).
Thuật toán Miller (1976): Hoàn toàn tất định và chạy trong thời gian đa thức ( $O(\log^4 n)$ ), nhưng tính đúng đắn lại phụ thuộc vào Giả thuyết Riemann Mở rộng (Generalized Riemann Hypothesis - GRH) — một giả thuyết toán học thế kỷ chưa được chứng minh.
Thuật toán APR-CL / ECPP (Elliptic Curve Primality Proving): Hoàn toàn tất định, không dựa vào giả thuyết chưa chứng minh, nhưng độ phức tạp là gần đa thức (Nearly-Polynomial) $O((\log n)^{c \log \log \log n})$ .

Tháng 8 năm 2002, ba nhà khoa học máy tính người Ấn Độ tại Viện Công nghệ IIT Kanpur — Manindra Agrawal, Neeraj Kayal và Nitin Saxena — đã công bố bài báo lịch sử "PRIMES is in P". Thuật toán mang tên họ — Thuật toán AKS — đã lần đầu tiên trong lịch sử nhân loại thỏa mãn đồng thời cả 4 tiêu chuẩn vàng:

Tổng quát (General): Áp dụng cho mọi số nguyên tự nhiên mà không cần dạng đặc biệt.
Thời gian đa thức (Polynomial-time): Bị chặn trên bởi $O(\log^c n)$ .
Tất định (Deterministic): Kết quả đúng đắn 100%, không có xác suất sai số.
Không điều kiện (Unconditional): Độc lập hoàn toàn với bất kỳ giả thuyết toán học chưa chứng minh nào.

1. Cơ sở Lý thuyết: Định lý Fermat mở rộng trên Vành Đa thức

Thuật toán AKS bắt nguồn từ một biến thể mở rộng của Định lý Fermat nhỏ sang vành đa thức hệ số nguyên $\mathbb{Z}[X]$ .

Định lý Đồng dư Đa thức Fermat

Định lý: Cho $n \ge 2$ và $a \in \mathbb{Z}$ thỏa mãn $\gcd(a, n) = 1$ . Khi đó, $n$ là một số nguyên tố khi và chỉ khi đồng dư thức sau được thỏa mãn trong vành đa thức $(\mathbb{Z}/n\mathbb{Z})[X]$ :

$(X + a)^n \equiv X^n + a \pmod n$

Chứng minh:

Khai triển nhị thức Newton cho vế trái:

$(X + a)^n = X^n + \sum_{k=1}^{n-1} \binom{n}{k} a^{n-k} X^k + a^n$

Chiều thuận ( $n$ là số nguyên tố):

Với mọi $1 \le k \le n-1$ , hệ số nhị thức $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ luôn có tử số chia hết cho $n$ trong khi mẫu số chỉ gồm các thừa số $< n$ . Vì $n$ nguyên tố, $n \mid \binom{n}{k}$ , suy ra mọi số hạng ở giữa đều đồng dư với $0 \pmod n$ . Theo Định lý Fermat nhỏ, $a^n \equiv a \pmod n$ . Do đó, $(X + a)^n \equiv X^n + a \pmod n$ .
Chiều nghịch ( $n$ là hợp số):

Giả sử $n$ là hợp số và $p$ là một ước nguyên tố của $n$ với lũy thừa cao nhất chia hết cho $n$ là $p^k$ ( $p^k \mid n$ nhưng $p^{k+1} \nmid n$ ). Khi xét hệ số của số hạng $X^p$ :

$\binom{n}{p} = \frac{n(n-1)\cdots(n-p+1)}{p!}$
Lũy thừa của $p$ chia hết $\binom{n}{p}$ nhỏ hơn lũy thừa của $p$ chia hết $n$ , dẫn đến hệ số này không thể chia hết cho $n$ . Do đó, đẳng thức đa thức bị vi phạm.

Nút thắt Tính toán (The Computational Bottleneck)

Mặc dù đồng dư thức $(X + a)^n \equiv X^n + a \pmod n$ là một điều kiện cần và đủ hoàn hảo, ta không thể kiểm tra trực tiếp nó:

Khai triển $(X + a)^n$ có tới $n + 1$ hệ số.
Với $n \approx 10^{100}$ , việc lưu trữ và tính toán $n$ hệ số đòi hỏi thời gian và bộ nhớ tỷ lệ thuận với $n$ — tức là hàm mũ theo độ dài bit đầu vào $\log_2 n$ .

2. Ý tưởng Đột phá AKS: Rút gọn Bậc bằng Đa thức $X^r - 1$

Để vượt qua rào cản hàm mũ, Agrawal, Kayal và Saxena đề xuất thực hiện phép chia lấy dư đa thức không chỉ theo modulo số nguyên $n$ , mà còn theo một đa thức triệt tiêu bậc nhỏ $X^r - 1$ :

$(X + a)^n \equiv X^n + a \pmod{X^r - 1, \, n}$

Phép chia lấy dư theo $X^r - 1$ tương đương với việc thay thế mọi lũy thừa $X^k$ bằng $X^{k \pmod r}$ .
Bậc của mọi đa thức trong quá trình tính toán luôn bị khống chế nghiêm ngặt trong khoảng $[0, r - 1]$ .
Khi sử dụng thuật toán lũy thừa nhị phân đa thức (Polynomial Binary Exponentiation), phép tính chỉ tốn $O(r^2 \log n)$ phép toán số học.

       Khai triển Fermat ngây thơ:                   Đột phá Rút gọn AKS:
              (X + a)^n                                   (X + a)^n mod (X^r - 1, n)
                  |                                                   |
      Bậc đa thức đạt tới n                               Bậc đa thức luôn <= r - 1
     (Hàm mũ: 10^100 hệ số)                               (Đa thức: chỉ r hệ số nhỏ)

Thách thức: Hợp số giả trang (Intruders)

Khi rút gọn theo modulo $X^r - 1$ , một số hợp số $n$ cũng có thể vô tình thỏa mãn đồng dư thức đối với một giá trị $a$ cụ thể.

Lời giải của nhóm tác giả AKS:

Bằng kỹ thuật đại số trừu tượng trên nhóm xyclic và trường hữu hạn, AKS đã chứng minh một định lý cốt lõi:

Nếu ta chọn được một số nguyên $r$ có cấp nhân $\text{ord}_r(n) > (\log_2 n)^2$ , và đồng dư thức:

$(X + a)^n \equiv X^n + a \pmod{X^r - 1, \, n}$
được thỏa mãn đồng thời cho đủ nhiều giá trị cơ sở $a$ :

$1 \le a \le \lfloor 2 \sqrt{\phi(r)} \log_2 n \rfloor$
thì số $n$ chắc chắn không thể là hợp số (ngoại trừ trường hợp $n$ là lũy thừa đúng của một số nguyên).

3. Toàn bộ Quy trình 6 Bước của Thuật toán AKS

Cho số nguyên $n \ge 2$ :

Bước 1: Kiểm tra Lũy thừa đúng (Perfect Power Test)

Kiểm tra xem $n$ có dạng $n = a^b$ với $a \ge 1$ và $b \ge 2$ hay không.

Dùng tìm kiếm nhị phân kiểm tra căn bậc $b$ của $n$ với mọi $2 \le b \le \lfloor \log_2 n \rfloor$ .
Nếu $n = a^b$ , kết luận $n$ là HỢP SỐ (COMPOSITE).

Bước 2: Tìm Số nguyên $r$ Thích hợp

Tìm số nguyên dương nhỏ nhất $r$ sao cho cấp nhân của $n$ modulo $r$ (ký hiệu $\text{ord}_r(n)$ ) thỏa mãn:

$\text{ord}_r(n) > (\log_2 n)^2$

Nghĩa là $n^k \not\equiv 1 \pmod r$ với mọi $1 \le k \le \lfloor (\log_2 n)^2 \rfloor$ .
AKS chứng minh được rằng luôn tồn tại một giá trị $r$ thỏa mãn với $r \le \lceil (\log_2 n)^5 \rceil$ .

Bước 3: Kiểm tra Ước chung nhỏ

Với mọi $2 \le a \le r$ :

Nếu $1 < \gcd(a, n) < n$ , kết luận $n$ là HỢP SỐ (COMPOSITE).

Bước 4: Xét trường hợp Biên

Nếu $n \le r$ , kết luận $n$ là SỐ NGUYÊN TỐ (PRIME) (vì $n$ đã vượt qua Bước 3, không chia hết cho bất kỳ số nào $\le n$ ).

Bước 5: Kiểm tra Đồng dư Đa thức

Đặt ngưỡng cận $L = \lfloor 2 \sqrt{\phi(r)} \log_2 n \rfloor$ (trong bài báo gốc) hoặc $L = \lfloor 2 \sqrt{r} \log_2 n \rfloor$ .

Với mỗi $a$ chạy từ $1$ đến $L$ :

Tính $P_1(X) = (X + a)^n \pmod{X^r - 1, \, n}$ bằng lũy thừa nhị phân đa thức.
Tính $P_2(X) = X^{n \pmod r} + a \pmod n$ .
Nếu $P_1(X) \neq P_2(X)$ , kết luận $n$ là HỢP SỐ (COMPOSITE).

Bước 6: Kết luận Cuối cùng

Nếu vượt qua toàn bộ các bước kiểm tra trên, $n$ chắc chắn là SỐ NGUYÊN TỐ (PRIME).

4. Hiện thực hóa Thuật toán AKS bằng Golang

Chương trình Golang dưới đây hiện thực hóa đầy đủ cấu trúc đại số và thuật toán AKS:

Thư viện đa thức trên vành $(\mathbb{Z}/n\mathbb{Z})[X] / (X^r - 1)$ .
Phép nhân đa thức tích chập vòng (Cyclic Convolution modulo $r$ ).
Lũy thừa nhị phân đa thức sử dụng math/big.
Pipeline 6 bước chuẩn xác của Agrawal-Kayal-Saxena.

package main

import (
	"fmt"
	"math"
	"math/big"
)

var (
	zero = big.NewInt(0)
	one  = big.NewInt(1)
)

// Polynomial biểu diễn đa thức bậc < r trên vành Z_n
// poly[i] là hệ số của X^i
type Polynomial struct {
	coeffs []*big.Int
	r      int
	n      *big.Int
}

func NewPolynomial(r int, n *big.Int) *Polynomial {
	c := make([]*big.Int, r)
	for i := 0; i < r; i++ {
		c[i] = new(big.Int)
	}
	return &Polynomial{coeffs: c, r: r, n: n}
}

// Mul nhân hai đa thức modulo (X^r - 1, n)
func (p *Polynomial) Mul(q *Polynomial) *Polynomial {
	res := NewPolynomial(p.r, p.n)

	for i := 0; i < p.r; i++ {
		if p.coeffs[i].Sign() == 0 {
			continue
		}
		for j := 0; j < p.r; j++ {
			if q.coeffs[j].Sign() == 0 {
				continue
			}
			// X^i * X^j = X^(i+j) == X^((i+j) mod r) (mod X^r - 1)
			idx := (i + j) % p.r
			term := new(big.Int).Mul(p.coeffs[i], q.coeffs[j])
			res.coeffs[idx].Add(res.coeffs[idx], term)
			res.coeffs[idx].Mod(res.coeffs[idx], p.n)
		}
	}
	return res
}

// PolyModPow tính P(X)^exp mod (X^r - 1, n)
func PolyModPow(base *Polynomial, exp *big.Int) *Polynomial {
	res := NewPolynomial(base.r, base.n)
	res.coeffs[0].SetInt64(1) // Đa thức đơn vị P(X) = 1

	curr := base
	expBits := exp.Text(2)

	for i := len(expBits) - 1; i >= 0; i-- {
		if expBits[i] == '1' {
			res = res.Mul(curr)
		}
		if i > 0 {
			curr = curr.Mul(curr)
		}
	}
	return res
}

// Hàm tính phi hàm Euler phi(n)
func eulerPhi(n int) int {
	result := n
	p := 2
	for p*p <= n {
		if n%p == 0 {
			for n%p == 0 {
				n /= p
			}
			result -= result / p
		}
		p++
	}
	if n > 1 {
		result -= result / n
	}
	return result
}

// Bước 1: Kiểm tra n có phải lũy thừa đúng a^b (b >= 2) hay không
func isPerfectPower(n *big.Int) bool {
	nFloat, _ := new(big.Float).SetInt(n).Float64()
	maxB := int(math.Ceil(math.Log2(nFloat)))

	for b := 2; b <= maxB; b++ {
		// Tìm căn bậc b của n bằng tìm kiếm nhị phân
		low := big.NewInt(2)
		high := new(big.Int).Set(n)
		bigB := big.NewInt(int64(b))

		for low.Cmp(high) <= 0 {
			mid := new(big.Int).Add(low, high)
			mid.Div(mid, big.NewInt(2))

			val := new(big.Int).Exp(mid, bigB, nil)
			cmp := val.Cmp(n)

			if cmp == 0 {
				return true
			} else if cmp < 0 {
				low.Add(mid, one)
			} else {
				high.Sub(mid, one)
			}
		}
	}
	return false
}

// AKSTest thực hiện kiểm tra tính nguyên tố bằng thuật toán AKS
func AKSTest(n *big.Int) bool {
	if n.Cmp(big.NewInt(2)) < 0 {
		return false
	}
	if n.Cmp(big.NewInt(2)) == 0 || n.Cmp(big.NewInt(3)) == 0 {
		return true
	}

	// 1. Kiểm tra Lũy thừa đúng
	if isPerfectPower(n) {
		return false
	}

	nFloat, _ := new(big.Float).SetInt(n).Float64()
	log2n := math.Log2(nFloat)
	log2nSq := log2n * log2n

	// 2. Tìm r nhỏ nhất sao cho ord_r(n) > (log2 n)^2
	maxK := int(math.Floor(log2nSq))
	r := 2
	for {
		gcdVal := new(big.Int).GCD(nil, nil, big.NewInt(int64(r)), n)
		if gcdVal.Cmp(one) > 0 && gcdVal.Cmp(n) < 0 {
			return false // Tìm thấy ước số
		}

		// Kiểm tra cấp nhân ord_r(n)
		ordGreaterThanLogSq := true
		rBig := big.NewInt(int64(r))
		for k := 1; k <= maxK; k++ {
			pw := new(big.Int).Exp(n, big.NewInt(int64(k)), rBig)
			if pw.Cmp(one) == 0 {
				ordGreaterThanLogSq = false
				break
			}
		}

		if ordGreaterThanLogSq {
			break
		}
		r++
	}

	// 3. Kiểm tra gcd(a, n) với mọi 2 <= a <= r
	for a := 2; a <= r; a++ {
		g := new(big.Int).GCD(nil, nil, big.NewInt(int64(a)), n)
		if g.Cmp(one) > 0 && g.Cmp(n) < 0 {
			return false
		}
	}

	// 4. Nếu n <= r, n là số nguyên tố
	if n.Cmp(big.NewInt(int64(r))) <= 0 {
		return true
	}

	// 5. Kiểm tra đồng dư đa thức (X + a)^n == X^n + a (mod X^r - 1, n)
	phiR := eulerPhi(r)
	limit := int(math.Floor(2.0 * math.Sqrt(float64(phiR)) * log2n))
	if limit == 0 {
		limit = 1
	}

	nModR := new(big.Int).Mod(n, big.NewInt(int64(r))).Int64()

	for a := 1; a <= limit; a++ {
		// Dựng đa thức cơ sở P(X) = X + a
		basePoly := NewPolynomial(r, n)
		basePoly.coeffs[1] = big.NewInt(1)
		basePoly.coeffs[0] = big.NewInt(int64(a))

		// Tính vế trái: (X + a)^n mod (X^r - 1, n)
		lhs := PolyModPow(basePoly, n)

		// Dựng vế phải: X^(n mod r) + a mod n
		rhs := NewPolynomial(r, n)
		rhs.coeffs[nModR].Add(rhs.coeffs[nModR], big.NewInt(1))
		rhs.coeffs[0].Add(rhs.coeffs[0], big.NewInt(int64(a)))
		rhs.coeffs[nModR].Mod(rhs.coeffs[nModR], n)
		rhs.coeffs[0].Mod(rhs.coeffs[0], n)

		// So sánh hai đa thức
		for i := 0; i < r; i++ {
			if lhs.coeffs[i].Cmp(rhs.coeffs[i]) != 0 {
				return false // Vi phạm đồng dư -> HỢP SỐ
			}
		}
	}

	// 6. Vượt qua mọi bài kiểm tra -> SỐ NGUYÊN TỐ
	return true
}

func main() {
	testCases := []int64{
		2, 3, 5, 17, 31, 101, 1009, // Số nguyên tố
		4, 9, 15, 27, 91, 561, 1000, // Hợp số (bao gồm số Carmichael 561)
	}

	fmt.Println("=== KIỂM TRA SỐ NGUYÊN TỐ BẰNG THUẬT TOÁN AKS ===")
	for _, num := range testCases {
		val := big.NewInt(num)
		isPrime := AKSTest(val)
		resultStr := "HỢP SỐ (Composite)"
		if isPrime {
			resultStr = "SỐ NGUYÊN TỐ (Prime)"
		}
		fmt.Printf("Số %5d : %s\n", num, resultStr)
	}
}

5. Phân tích Độ phức tạp và Tiến trình Cải tiến Lịch sử

Phiên bản / Tác giả	Năm	Độ phức tạp thời gian	Kỹ thuật cốt lõi
Agrawal, Kayal, Saxena (Bản gốc)	2002	$\tilde{O}(\log^{12} n)$	Tìm $r = O(\log^5 n)$ và cận $L = O(\sqrt{r} \log n)$
AKS (Bản hoàn thiện)	2004	$\tilde{O}(\log^{10.5} n)$	Tinh chỉnh định lý nhóm xyclic
H. W. Lenstra Jr.	2002	$\tilde{O}(\log^{8} n)$	Tối ưu hóa cấu trúc tự đẳng cấu trường
Lenstra & Carl Pomerance	2005	$\tilde{O}(\log^6 n)$	Khảo sát vành mở rộng và nghiệm nguyên thủy
Nếu Giả thuyết số nguyên tố sinh đôi đúng	—	$\tilde{O}(\log^3 n)$	Cận kích thước của $r$ giảm xuống $O(\log^2 n)$

Ký hiệu $\tilde{O}(f(n))$ đại diện cho $O(f(n) \cdot \text{poly}(\log f(n)))$ — bỏ qua các thừa số logarit bậc thấp.

Tại sao AKS đạt thời gian đa thức?

Bước 2 tìm được $r \le O(\log^5 n)$ .
Vòng lặp Bước 5 chạy qua $L = O(\sqrt{r} \log n) = O(\log^{3.5} n)$ giá trị của $a$ .
Trong mỗi lượt của Bước 5, phép lũy thừa nhị phân đa thức nhân hai đa thức bậc $r$ tốn $O(r \log r)$ (dùng FFT) và lặp lại $O(\log n)$ lần.
Tích các thành phần mang lại hàm đa thức thuần túy theo kích thước bit $\log n$ , chính thức khép lại bài toán thiên niên kỷ: $\text{PRIMES} \in \text{P}$ .

6. So sánh Toàn diện: Tại sao Miller-Rabin vẫn là Vua của Thực tế?

Mặc dù AKS là phát minh thế kỷ về mặt lý thuyết, trong toàn bộ các hệ điều hành, thư viện mật mã công nghiệp (OpenSSL, Go crypto/rand, BouncyCastle, GMP), Miller-Rabin và Baillie-PSW mới là các thuật toán được sử dụng trên thực tế, hoàn toàn không dùng AKS.

Tiêu chí	Miller-Rabin	Baillie-PSW	Thuật toán AKS
Bản chất	Ngẫu nhiên hóa (Monte Carlo)	Tất định kết hợp (Fermat + Lucas)	Tất định tuyệt đối
Cơ sở lý thuyết	Giả thuyết / Xác suất độc lập	Chưa phát hiện phản ví dụ	Đã chứng minh 100% trong P
Độ phức tạp	$O(k \log^2 n)$ (với FFT)	$O(\log^2 n)$	$\tilde{O}(\log^6 n)$
Thời gian chạy với số 2048-bit	$< 0.001$ giây	$< 0.005$ giây	Hàng giờ đến hàng ngày
Xác suất sai số	$\le 4^{-k}$ (với $k = 40$ : $< 10^{-24}$ )	$0$ với mọi số $< 2^{64}$	0 (Không sai số)

Nghịch lý Thực hành:

Với một số nguyên 2048-bit (cỡ khóa RSA chuẩn), $(\log_2 n)^6 \approx (2048)^6 \approx 7.3 \times 10^{19}$ phép tính — một con số khổng lồ đối với bất kỳ CPU đơn lẻ nào. Trong khi đó, Miller-Rabin với 40 vòng lặp chỉ tốn vài triệu phép tính vi xử lý và có xác suất sai số $4^{-40} \approx 10^{-24}$ (thấp hơn nhiều so với xác suất một tia vũ trụ làm lật bit RAM của máy chủ).
Giá trị đích thực của AKS:

AKS không sinh ra để thay thế Miller-Rabin trong các hệ thống nhúng tốc độ cao. Giá trị của AKS nằm ở việc giải quyết câu hỏi nền tảng của lý thuyết độ phức tạp tính toán: Phân loại chính xác bài toán kiểm tra số nguyên tố vào lớp $\mathbf{P}$ , hoàn thiện bức tranh toán học của nhân loại mà không còn bất kỳ dấu hỏi nghi ngờ nào.

cấu trúc dữ liệu