14.3K 216 1.7K

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

Cấu trúc dữ liệu và Giải thuật Bài 150: Phương pháp Phân tích Thừa số Đường cong Elliptic (Lenstra's Elliptic Curve Factorization - ECM) - Khi hình học đại số kết hợp lý thuyết nhóm giải bài toán thừa số nguyên tố.

Ở Bài 149, chúng ta đã nghiên cứu Sàng trường số đại số tổng quát (GNFS) — thuật toán có độ phức tạp $L_N[1/3]$ mạnh nhất để phân tích một hợp số $N$ . Tuy nhiên, GNFS có một đặc tính cố hữu: độ phức tạp thời gian phụ thuộc hoàn toàn vào độ lớn của hợp số $N$ , bất kể các ước số nguyên tố của nó lớn hay nhỏ. Nếu $N$ là một số 1000 bit nhưng lại chứa một thừa số nguyên tố $p$ chỉ khoảng 40 chữ số thập phân (130 bit), việc kích hoạt toàn bộ cỗ máy GNFS là vô cùng tốn kém và lãng phí.

Năm 1987, nhà toán học người Hà Lan Hendrik Lenstra đã công bố một phát minh mang tính bước ngoặt: Thuật toán Phân tích Thừa số Đường cong Elliptic (Lenstra ECM). Bằng cách thay thế nhóm nhân hữu hạn $(\mathbb{Z}/p\mathbb{Z})^*$ trong thuật toán Pollard's $p-1$ bằng nhóm các điểm trên đường cong Elliptic $E(\mathbb{F}_p)$ , Lenstra đã tạo ra một thuật toán có độ phức tạp dưới hàm mũ chỉ phụ thuộc vào kích thước của ước nguyên tố nhỏ nhất $p$ :

$L_p\left[1/2, \sqrt{2}\right] = \exp\left( (\sqrt{2} + o(1)) \sqrt{\ln p \ln \ln p} \right)$

Cho đến nay, ECM vẫn là thuật toán phân tích số nhanh thứ ba từng được biết đến (sau GNFS và SNFS), và giữ vị trí vô địch tuyệt đối trong việc tìm kiếm các ước số nguyên tố có kích thước lên tới 50–70 chữ số thập phân nằm bên trong các hợp số khổng lồ hàng nghìn bit.

1. Nguồn cảm hứng: Từ Bế tắc của Pollard's $p-1$ đến Ý tưởng của Lenstra

Nhắc lại Thuật toán Pollard's $p-1$

Thuật toán Pollard's $p-1$ (1974) dựa trên Định lý Fermat nhỏ: Nếu $p$ là một ước nguyên tố của $N$ , thì với mọi số nguyên $a$ thỏa mãn $\gcd(a, p) = 1$ :

$a^{p-1} \equiv 1 \pmod p$

Nếu $p - 1$ là một số $B$ -trơn ( $B$ -smooth) (tức là mọi ước nguyên tố của $p - 1$ đều nhỏ hơn hoặc bằng $B$ ), thì số $k = \text{lcm}(1, 2, \dots, B)$ sẽ là một bội số của $p - 1$ . Khi đó:

$a^k \equiv 1 \pmod p \implies p \mid (a^k - 1)$

Tính $g = \gcd(a^k - 1, N)$ . Nếu $1 < g < N$ , ta tìm được thừa số $p$ .

Điểm nghẽn chí mạng của Pollard's $p-1$

Nhóm nhân $(\mathbb{Z}/p\mathbb{Z})^*$ là duy nhất và có cấp cố định chính xác bằng $p - 1$ .

Nếu $p - 1$ tình cờ chứa một ước nguyên tố lớn (ví dụ $p = 2q + 1$ với $q$ là số nguyên tố an toàn - Safe Prime), thuật toán Pollard's $p-1$ hoàn toàn bất lực.
Người thực hiện không có cách nào thay đổi cấu trúc của nhóm $(\mathbb{Z}/p\mathbb{Z})^*$ . Một khi $p - 1$ không trơn, thuật toán thất bại vĩnh viễn.

Đột phá của Hendrik Lenstra

Thay vì làm việc trên nhóm $(\mathbb{Z}/p\mathbb{Z})^*$ , Lenstra đề xuất làm việc trên nhóm các điểm của một đường cong Elliptic $E$ trên trường hữu hạn $\mathbb{F}_p$ .

Theo Định lý Hasse về Đường cong Elliptic (Hasse's Bound), số lượng điểm của nhóm $E(\mathbb{F}_p)$ (ký hiệu là $\#E(\mathbb{F}_p)$ ) không cố định, mà dao động trong một khoảng xác định quanh $p + 1$ :

p + 1 - 2\sqrt{p} \le #E(\mathbb{F}_p) \le p + 1 + 2\sqrt{p}

Ý tưởng thiên tài của Lenstra:

Nếu đường cong $E_1$ có cấp $\#E_1(\mathbb{F}_p)$ không trơn, ta không hề bị bế tắc! Ta chỉ việc chọn ngẫu nhiên một đường cong $E_2$ khác (thay đổi các hệ số $a, b$ ). Cấp của đường cong mới $\#E_2(\mathbb{F}_p)$ sẽ nhận một giá trị ngẫu nhiên khác trong khoảng Hasse.

Bằng cách thử nhiều đường cong độc lập, theo quy luật xác suất, ta chắc chắn sẽ tìm được một đường cong mà cấp của nó là số $B$ -trơn!

   Pollard's p-1:
   Nhóm nhân (Z/pZ)*  ---> Cấp cố định p - 1  ---> Nếu không trơn => THẤT BẠI HOÀN TOÀN
   
   Lenstra ECM:
   Đường cong E_1      ---> Cấp N_1 ∈ [p+1 - 2√p, p+1 + 2√p]  ---> Không trơn?
   Đường cong E_2      ---> Cấp N_2 ∈ [p+1 - 2√p, p+1 + 2√p]  ---> Không trơn?
   ...
   Đường cong E_k      ---> Cấp N_k là B-trơn!                ---> THÀNH CÔNG!

2. Hình học Đại số: Luật cộng trên Đường cong Elliptic modulo $N$

Một đường cong Elliptic $E$ trên vành $\mathbb{Z}/N\mathbb{Z}$ (với $\gcd(6, N) = 1$ ) ở dạng chuẩn Weierstrass rút gọn có phương trình:

$y^2 = x^3 + ax + b \pmod N$

với biệt thức $\Delta = -16(4a^3 + 27b^2) \not\equiv 0 \pmod N$ .

Tập hợp các điểm trên đường cong cùng với Điểm vô cực $\mathcal{O}$ (đóng vai trò là phần tử trung hòa của phép cộng) tạo thành một nhóm giao hoán (Abelian Group).

Công thức Cộng Điểm (Chord-and-Tangent Group Law)

Cho hai điểm $P = (x_1, y_1)$ và $Q = (x_2, y_2)$ trên đường cong:

Phần tử nghịch đảo: $-P = (x_1, -y_1 \pmod N)$ . Nếu $x_1 = x_2$ và $y_1 \equiv -y_2 \pmod N$ , thì $P + Q = \mathcal{O}$ .
Hệ số góc của tiếp tuyến hoặc cát tuyến ( $\lambda$ ):
- Nếu $P \neq Q$ (Cộng hai điểm khác nhau - Addition):
  
  $\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod N$
- Nếu $P = Q$ (Nhân đôi một điểm - Doubling):
  
  $\lambda = \frac{3x_1^2 + a}{2y_1} \pmod N$
Tọa độ của điểm tổng $R = P + Q = (x_3, y_3)$ :

$x_3 = \lambda^2 - x_1 - x_2 \pmod N$
$y_3 = \lambda(x_1 - x_3) - y_1 \pmod N$

          y ^
            |           . * (Tangent / Chord)
            |       .  /
            |     .   / 
            |   .    P(x1, y1)
            |  .    /
            | .    /
            +-----+-------Q(x2, y2)------> x
            |  .   \
            |   .   \
            |    .   R'(x3, -y3)
            |     .   \
            |          R(x3, y3) = P + Q

3. Cơ chế Khai thác: Khi "Thất bại" Phép tính trở thành Thành công

Lưu ý rằng $N = p \cdot q$ là một hợp số, do đó $\mathbb{Z}/N\mathbb{Z}$ không phải là một trường (Field) mà chỉ là một vành giao hoán (Ring). Một số phần tử trong $\mathbb{Z}/N\mathbb{Z}$ không có nghịch đảo nhân!

Khi tính toán hệ số góc $\lambda = \frac{\Delta y}{\Delta x} \pmod N$ :

Ta cần tìm nghịch đảo modulo $N$ của mẫu số $D = \Delta x$ (hoặc $D = 2y_1$ ).
Để tính $D^{-1} \pmod N$ , ta áp dụng Thuật toán Euclid mở rộng để tìm $g = \gcd(D, N)$ .

Xuất hiện 3 kịch bản:

$g = 1$ : $D$ nguyên tố cùng nhau với $N$ . Phép nghịch đảo $D^{-1} \pmod N$ tồn tại và duy nhất. Phép cộng điểm trên đường cong diễn ra bình thường.
$1 < g < N$ : Phép tính nghịch đảo thất bại, nhưng ta lập tức phân tích thành công $N$ ! Vì $g$ chia hết cho $N$ và $1 < g < N$ , nên $g$ chính là một thừa số không tầm thường của $N$ .
$g = N$ : Điểm $P$ đồng thời triệt tiêu về vô cực trên cả hai ước số. Ta hủy đường cong hiện tại và chọn đường cong mới.

Trực giác toán học: Khi cấp của nhóm $\#E(\mathbb{F}_p)$ chia hết cho hệ số nhân $k$ , phép nhân vô hướng $k \cdot P$ sẽ biến điểm $P$ thành Điểm vô cực $\mathcal{O}$ trên trường con $\mathbb{F}_p$ . Nhưng trên trường con $\mathbb{F}_q$ , điểm này vẫn là một điểm hữu hạn bình thường. Tọa độ của điểm rơi vào trạng thái "vừa là vô cực modulo $p$ , vừa là hữu hạn modulo $q$ ". Trạng thái phân rã này buộc mẫu số $D$ phải chia hết cho $p$ nhưng không chia hết cho $q$ , khiến $\gcd(D, N) = p$ xuất hiện tự nhiên!

4. Thuật toán Lenstra ECM Toàn diện (Giai đoạn 1 & Giai đoạn 2)

Giai đoạn 1 (Stage 1)

Chọn một cận trơn $B_1$ (ví dụ: $B_1 = 2000$ cho các ước 30 bit; $B_1 = 10^6$ cho các ước 100 bit).
Chọn ngẫu nhiên một điểm $P = (x_0, y_0)$ và một hệ số $a \in \mathbb{Z}/N\mathbb{Z}$ .
Tính hệ số $b = y_0^2 - x_0^3 - a x_0 \pmod N$ để đảm bảo điểm $P$ luôn nằm trên đường cong $E$ .
Kiểm tra $\gcd(4a^3 + 27b^2, N)$ : Nếu $> 1$ , ta tìm được thừa số ngay; nếu bằng $N$ , chọn lại.
Tính bội số tích lũy:

$k = \prod_{q \le B_1, q \text{ prime}} q^{\lfloor \frac{\ln B_1}{\ln q} \rfloor}$
Thực hiện nhân vô hướng $Q = k \cdot P \pmod N$ bằng cách lần lượt nhân với từng lũy thừa số nguyên tố $q^e$ :
- Ở mỗi bước cộng điểm hoặc nhân đôi điểm trong thuật toán Double-and-Add, nếu gặp phép tính nghịch đảo $\gcd(D, N) > 1$ : dừng lại và trả về ước số $g$ .

Giai đoạn 2 (Stage 2 - Two-Stage ECM)

Nếu sau Giai đoạn 1 mà vẫn chưa tìm được ước, cấp của nhóm $\#E(\mathbb{F}_p)$ có thể có dạng:

#E(\mathbb{F}_p) = M \cdot q

với $M$ là số $B_1$ -trơn, còn $q$ là một số nguyên tố đơn lẻ nằm trong khoảng $[B_1, B_2]$ (với $B_2 \approx 100 \cdot B_1$ ).

Điểm $Q = k \cdot P$ từ Giai đoạn 1 đã triệt tiêu phần $B_1$ -trơn $M$ (tức là $Q$ có cấp đúng bằng $q$ trên $\mathbb{F}_p$ ).
Trong Giai đoạn 2, ta kiểm tra xem có tồn tại số nguyên tố $q \in [B_1, B_2]$ sao cho $q \cdot Q = \mathcal{O} \pmod p$ hay không.
Áp dụng kỹ thuật Baby-step Giant-step để tính toán nhanh tích khoảng cách giữa các điểm nguyên tố, giảm độ phức tạp của Giai đoạn 2 từ $O(B_2 - B_1)$ xuống $O(\sqrt{B_2})$ .

5. Hiện thực hóa Thuật toán Lenstra ECM bằng Golang

Chương trình Golang dưới đây cài đặt hoàn chỉnh:

Cấu trúc số nguyên lớn math/big hỗ trợ các số nguyên có kích thước tùy ý.
Phép nhân đôi (Doubling) và Phép cộng (Addition) với cơ chế bẫy lỗi nghịch đảo Euclid mở rộng để trích xuất ước số.
Thuật toán nhân vô hướng Double-and-Add.
Vòng lặp thử nghiệm đa đường cong Lenstra ECM Stage 1.

package main

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

var (
	zero = big.NewInt(0)
	one  = big.NewInt(1)
	two  = big.NewInt(2)
	three = big.NewInt(3)
)

// Point biểu diễn một điểm (X, Y) trên đường cong Elliptic
// IsInfinity = true đại diện cho điểm vô cực O
type Point struct {
	x, y       *big.Int
	isInfinity bool
}

func NewPoint(x, y *big.Int) Point {
	return Point{
		x:          new(big.Int).Set(x),
		y:          new(big.Int).Set(y),
		isInfinity: false,
	}
}

func Infinity() Point {
	return Point{x: nil, y: nil, isInfinity: true}
}

// EllipticCurve biểu diễn y^2 = x^3 + a*x + b (mod N)
type EllipticCurve struct {
	a, b *big.Int
	n    *big.Int
}

// FactorFoundError là một ngoại lệ có chủ đích khi nghịch đảo modulo thất bại
type FactorFoundError struct {
	Factor *big.Int
}

func (e *FactorFoundError) Error() string {
	return fmt.Sprintf("Tìm thấy thừa số nguyên tố không tầm thường: %s", e.Factor.String())
}

// modularInverse tính nghịch đảo modulo N. Nếu gcd(val, N) > 1, trả về FactorFoundError
func (c *EllipticCurve) modularInverse(val *big.Int) (*big.Int, error) {
	v := new(big.Int).Mod(val, c.n)
	g := new(big.Int).GCD(nil, nil, v, c.n)

	if g.Cmp(one) > 0 && g.Cmp(c.n) < 0 {
		return nil, &FactorFoundError{Factor: g}
	}
	if g.Cmp(c.n) == 0 {
		return nil, fmt.Errorf("Điểm suy biến hoàn toàn mod N")
	}

	inv := new(big.Int).ModInverse(v, c.n)
	return inv, nil
}

// Add cộng hai điểm P và Q trên đường cong modulo N
func (c *EllipticCurve) Add(P, Q Point) (Point, error) {
	if P.isInfinity {
		return Q, nil
	}
	if Q.isInfinity {
		return P, nil
	}

	// Kiểm tra nếu P == -Q
	diffY := new(big.Int).Add(P.y, Q.y)
	diffY.Mod(diffY, c.n)
	if P.x.Cmp(Q.x) == 0 && diffY.Sign() == 0 {
		return Infinity(), nil
	}

	var lambda *big.Int

	if P.x.Cmp(Q.x) == 0 && P.y.Cmp(Q.y) == 0 {
		// Nhân đôi điểm (P == Q): lambda = (3*x1^2 + a) / (2*y1) mod N
		num := new(big.Int).Mul(P.x, P.x)
		num.Mul(num, three)
		num.Add(num, c.a)
		num.Mod(num, c.n)

		denom := new(big.Int).Mul(two, P.y)
		denom.Mod(denom, c.n)

		invDenom, err := c.modularInverse(denom)
		if err != nil {
			return Infinity(), err
		}

		lambda = new(big.Int).Mul(num, invDenom)
		lambda.Mod(lambda, c.n)
	} else {
		// Cộng hai điểm khác nhau: lambda = (y2 - y1) / (x2 - x1) mod N
		num := new(big.Int).Sub(Q.y, P.y)
		num.Mod(num, c.n)

		denom := new(big.Int).Sub(Q.x, P.x)
		denom.Mod(denom, c.n)

		invDenom, err := c.modularInverse(denom)
		if err != nil {
			return Infinity(), err
		}

		lambda = new(big.Int).Mul(num, invDenom)
		lambda.Mod(lambda, c.n)
	}

	// x3 = lambda^2 - x1 - x2 mod N
	x3 := new(big.Int).Mul(lambda, lambda)
	x3.Sub(x3, P.x)
	x3.Sub(x3, Q.x)
	x3.Mod(x3, c.n)

	// y3 = lambda*(x1 - x3) - y1 mod N
	y3 := new(big.Int).Sub(P.x, x3)
	y3.Mul(lambda, y3)
	y3.Sub(y3, P.y)
	y3.Mod(y3, c.n)

	return NewPoint(x3, y3), nil
}

// ScalarMul tính k * P bằng thuật toán Double-and-Add
func (c *EllipticCurve) ScalarMul(k *big.Int, P Point) (Point, error) {
	R := Infinity()
	curr := P

	kBits := k.Text(2)
	for i := len(kBits) - 1; i >= 0; i-- {
		if kBits[i] == '1' {
			var err error
			R, err = c.Add(R, curr)
			if err != nil {
				return Infinity(), err
			}
		}
		var err error
		curr, err = c.Add(curr, curr)
		if err != nil {
			return Infinity(), err
		}
	}

	return R, nil
}

// Sàng số nguyên tố đơn giản sinh các số nguyên tố <= B
func sieveOfEratosthenes(limit int) []int64 {
	isPrime := make([]bool, limit+1)
	for i := 2; i <= limit; i++ {
		isPrime[i] = true
	}
	for p := 2; p*p <= limit; p++ {
		if isPrime[p] {
			for i := p * p; i <= limit; i += p {
				isPrime[i] = false
			}
		}
	}
	var primes []int64
	for p := 2; p <= limit; p++ {
		if isPrime[p] {
			primes = append(primes, int64(p))
		}
	}
	return primes
}

// LenstraECM thực thi thuật toán phân tích số
func LenstraECM(N *big.Int, B1 int, maxCurves int) (*big.Int, error) {
	// Kiểm tra chia hết cho 2 hoặc 3
	if new(big.Int).Mod(N, two).Sign() == 0 {
		return two, nil
	}
	if new(big.Int).Mod(N, three).Sign() == 0 {
		return three, nil
	}

	primes := sieveOfEratosthenes(B1)

	for curveIdx := 1; curveIdx <= maxCurves; curveIdx++ {
		// 1. Sinh ngẫu nhiên tọa độ điểm xuất phát P = (x0, y0) và tham số a
		x0, _ := rand.Int(rand.Reader, N)
		y0, _ := rand.Int(rand.Reader, N)
		a, _ := rand.Int(rand.Reader, N)

		// 2. Tính b = y0^2 - x0^3 - a*x0 mod N
		y2 := new(big.Int).Mul(y0, y0)
		x3 := new(big.Int).Mul(x0, x0)
		x3.Mul(x3, x0)
		ax := new(big.Int).Mul(a, x0)

		b := new(big.Int).Sub(y2, x3)
		b.Sub(b, ax)
		b.Mod(b, N)

		// 3. Kiểm tra biệt thức Delta = 4a^3 + 27b^2 mod N
		disc4a3 := new(big.Int).Mul(a, a)
		disc4a3.Mul(disc4a3, a)
		disc4a3.Mul(disc4a3, big.NewInt(4))

		disc27b2 := new(big.Int).Mul(b, b)
		disc27b2.Mul(disc27b2, big.NewInt(27))

		delta := new(big.Int).Add(disc4a3, disc27b2)
		delta.Mod(delta, N)

		g := new(big.Int).GCD(nil, nil, delta, N)
		if g.Cmp(one) > 0 && g.Cmp(N) < 0 {
			return g, nil // May mắn tìm thấy ước ngay khi sinh đường cong
		}
		if g.Cmp(N) == 0 {
			continue // Đường cong suy biến, chọn lại
		}

		curve := &EllipticCurve{a: a, b: b, n: N}
		P := NewPoint(x0, y0)

		// 4. Giai đoạn 1: Nhân tích lũy các lũy thừa số nguyên tố q^e <= B1
		currentPoint := P
		factorFound := false
		var discoveredFactor *big.Int

		for _, p := range primes {
			// Tính p^e <= B1 lớn nhất
			pPower := p
			for pPower*p <= int64(B1) {
				pPower *= p
			}

			k := big.NewInt(pPower)
			nextPoint, err := curve.ScalarMul(k, currentPoint)
			if err != nil {
				if fErr, ok := err.(*FactorFoundError); ok {
					discoveredFactor = fErr.Factor
					factorFound = true
					break
				}
				// Gặp lỗi suy biến mod N, bỏ qua đường cong này
				break
			}
			currentPoint = nextPoint
		}

		if factorFound {
			return discoveredFactor, nil
		}
	}

	return nil, fmt.Errorf("Không tìm thấy ước số sau %d đường cong với B1 = %d", maxCurves, B1)
}

func main() {
	// Khởi tạo hợp số N gồm hai số nguyên tố 30-bit:
	// p = 1000000007 (Prime 30-bit)
	// q = 1000000009 (Prime 30-bit)
	// N = 1000000016000000063 (Số 60-bit)
	pTrue := big.NewInt(1000000007)
	qTrue := big.NewInt(1000000009)
	N := new(big.Int).Mul(pTrue, qTrue)

	fmt.Printf("=== PHÂN TÍCH THỪA SỐ BẰNG THUẬT TOÁN LENSTRA ECM ===\n")
	fmt.Printf("Hợp số mục tiêu N = %s (Độ dài: %d bit)\n", N.String(), N.BitLen())
	fmt.Printf("Ước nguyên tố kỳ vọng: p = %s, q = %s\n\n", pTrue.String(), qTrue.String())

	B1 := 2000         // Cận trơn B1 cho ước số 30-bit
	maxCurves := 50     // Thử tối đa 50 đường cong ngẫu nhiên

	fmt.Printf("Bắt đầu thực thi ECM với B1 = %d, số đường cong tối đa = %d...\n", B1, maxCurves)
	factor, err := LenstraECM(N, B1, maxCurves)

	if err != nil {
		fmt.Printf("[THẤT BẠI] %v\n", err)
	} else {
		otherFactor := new(big.Int).Div(N, factor)
		fmt.Printf("\n[THÀNH CÔNG] Đã phân tích thành công hợp số N:\n")
		fmt.Printf("  -> Thừa số thứ nhất: %s\n", factor.String())
		fmt.Printf("  -> Thừa số thứ hai:   %s\n", otherFactor.String())
		fmt.Printf("  -> Kiểm tra nhân lại: %t\n",
			new(big.Int).Mul(factor, otherFactor).Cmp(N) == 0)
	}
}

6. Tối ưu hóa Thực tế: Tọa độ Chiếu Montgomery (Montgomery Ladder)

Trong mã nguồn thực tế của các thư viện hàng đầu như GMP-ECM, dạng phương trình Weierstrass $y^2 = x^3 + ax + b$ không được sử dụng vì nó đòi hỏi tính toán cả tọa độ $y$ và thực hiện phép nghịch đảo modulo trong từng bước cộng.

Thay vào đó, thuật toán sử dụng Đường cong Montgomery:

$B y^2 = x^3 + A x^2 + x$

chuyển sang Tọa độ Chiếu (Projective Coordinates) $(X : Z)$ với $x = X / Z$ :

Loại bỏ hoàn toàn biến $y$ : Điểm $P$ chỉ cần biểu diễn bằng cặp $(X_P : Z_P)$ .
Montgomery Ladder: Phép nhân vô hướng $k \cdot P$ chỉ sử dụng các phép tính cộng, trừ và nhân số nguyên lớn:
- Nhân đôi điểm ( $2P$ ): Tốn đúng 2 phép nhân và 2 phép bình phương ( $2M + 2S$ ).
- Cộng hai điểm khi biết trước hiệu ( $P + Q$ biết $P - Q$ ): Tốn $4M + 2S$ .
Không cần phép chia modular trong suốt Giai đoạn 1:

Thay vì tính nghịch đảo modulo ở từng bước, ta liên tục nhân dồn các mẫu số $Z$ vào một biến tích lũy duy nhất:

$\Pi \gets (\Pi \cdot Z) \pmod N$
Đến cuối cùng, ta chỉ cần gọi duy nhất một lần hàm $\gcd(\Pi, N)$ để kiểm tra toàn bộ quá trình, giúp tăng tốc độ thực thi lên gấp 10 đến 20 lần.

7. Phân tích Độ phức tạp và Bảng So sánh Thuật toán

Thuật toán	Phân loại	Độ phức tạp thời gian	Phụ thuộc vào	Ưu ứng dụng tối ưu nhất
Trial Division	Xác định	$O(\sqrt{N})$	$N$	Các ước cực nhỏ $< 10^6$
Pollard's $\rho$	Ngẫu nhiên hóa	$O(p^{1/2})$	$p$	Ước nhỏ đến vừa ( $< 40$ bit)
Pollard's $p-1$	Đại số	$O(B \log B)$	$p - 1$	Khi $p-1$ là số $B$ -trơn
Lenstra ECM	Hình học đại số	$L_p[1/2, \sqrt{2}]$	$p$ (Ước nhỏ nhất)	Tìm ước $p \le 60\text{--}80$ digits trong số khổng lồ
Quadratic Sieve (QS)	Đại số (Sàng)	$L_N[1/2, 1]$	$N$ (Toàn bộ)	Hợp số $N \le 100$ digits không có ước nhỏ
GNFS	Đại số (Trường số)	$L_N[1/3, 1.923]$	$N$ (Toàn bộ)	Hợp số $N > 110$ digits (Phá vỡ RSA)

Tham số Lựa chọn Khuyến nghị cho ECM

Kích thước ước $p$ (chữ số)	Kích thước ước $p$ (bit)	Cận trơn $B_1$	Cận trơn $B_2$	Số đường cong dự kiến
15 digits	~50 bit	$2.000$	$10^5$	~25
25 digits	~83 bit	$50.000$	$5 \times 10^6$	~160
35 digits	~116 bit	$10^6$	$10^8$	~1.000
45 digits	~150 bit	$1.1 \times 10^7$	$10^9$	~4.400
55 digits	~182 bit	$1.1 \times 10^8$	$10^{10}$	~18.000
65 digits	~215 bit	$8.5 \times 10^8$	$10^{11}$	~70.000

8. Ứng dụng Thực tế

Giai đoạn Tiền xử lý (Pre-testing) bắt buộc trong GNFS: Khi phân tích các số nguyên lớn của dự án RSA Challenge hay GIMPS, người ta không bao giờ chạy trực tiếp GNFS ngay từ đầu. Bước chuẩn mực luôn là chạy Lenstra ECM với các cận $B_1$ tăng dần để "quét sạch" mọi ước nguyên tố tiềm năng dưới 60 chữ số. Nếu loại bỏ được một ước 40 chữ số, kích thước phần còn lại của $N$ giảm đi đáng kể, giúp tiết kiệm hàng trăm năm CPU khi chạy GNFS sau đó.
Phân tích các số Fermat ( $F_m = 2^{2^m} + 1$ ): Năm 1999, Richard Brent sử dụng ECM tìm ra ước số 40 chữ số của số Fermat thứ 10 ( $F_{10}$ ). Đây là minh chứng rõ nhất cho sức mạnh của ECM: $F_{10}$ có kích thước lên tới 309 chữ số thập phân (vượt xa tầm với của bất kỳ thuật toán sàng nào thời bấy giờ), nhưng ECM đã bóc tách thành công nhờ tính chất chỉ phụ thuộc vào $p$ .
Phát hiện Lỗ hổng sinh khóa RSA yếu: Một số thiết bị phần cứng (như thẻ thông minh Smart Card, vi điều khiển IoT) bị lỗi bộ sinh số ngẫu nhiên khiến một trong hai số nguyên tố $p$ hoặc $q$ bị lệch kích thước nghiêm trọng (Unbalanced RSA - ví dụ $p$ có 150 bit, $q$ có 1898 bit để tạo khóa 2048-bit). Các khóa này hoàn toàn miễn nhiễm với GNFS nhưng bị bẻ gãy bởi Lenstra ECM chỉ trong vài phút.

cấu trúc dữ liệu

1. Nguồn cảm hứng: Từ Bế tắc của Pollard's p−1p-1p−1 đến Ý tưởng của Lenstra

Nhắc lại Thuật toán Pollard's p−1p-1p−1

Điểm nghẽn chí mạng của Pollard's p−1p-1p−1