General Number Field Sieve (GNFS): Họ đã phá RSA thế nào?

Motivation

Nếu mình đưa cho bạn hai số nguyên tố lớn $p$ và $q$, việc tính tích $n = p \cdot q$ chỉ mất vài micro giây trên bất kỳ máy tính nào. Nhưng nếu mình đưa cho bạn số $n$ và yêu cầu tìm ngược lại $p$ và $q$, bạn đang đối mặt với một bức tường thép đã bảo vệ nền tài chính và dữ liệu toàn cầu trong hơn 4 thập kỷ qua. Ví dụ, chúng ta có thể tính $97 \times 101 = 9,797$ trong tích tắc, nhưng nếu hỏi rằng $9,797$ có thể phân tích thành mấy nhân với mấy thì rất khó trả lời.

Hệ thống mật mã RSA – thứ đang bảo mật các giao dịch ngân hàng, chữ ký số và kết nối HTTPS của bạn – dựa hoàn toàn vào giả định rằng việc phân tích một số nguyên cực lớn (khoảng 2048-bit trở lên) là bất khả thi trong thời gian thực. Tuy nhiên, "bất khả thi" là một khái niệm mang tính thời điểm. Từ những phương pháp thô sơ ban đầu bằng cách bruteforce đơn giản (thử lần lượt lấy số đã cho chia cho $2,3,4,...\dots$ cho đến khi tìm ra kết quả), các nhà toán học đã không ngừng tìm kiếm những "vết nứt" trên bức tường RSA. Trong những nỗ lực tìm kiếm ấy, nhân loại đã tìm ra một số thuật toán quan trọng để giải quyết vấn đề này:

• Trial Division: Chỉ hiệu quả với các số rất nhỏ.

• Pollard's rho: Tốt để tìm các nhân tử nhỏ

• Quadratic Sieve (QS): Từng là "ông vua" tốc độ vào những năm 1980, hoạt động dựa trên việc tìm các số chính phương modulo $n$.

Khi các phương pháp truyền thống như Quadratic Sieve (Sàng bình phương) bắt đầu chạm ngưỡng giới hạn với các số nguyên trên 100 chữ số, cộng đồng toán học cần một công cụ mạnh mẽ hơn. Đó là lúc General Number Field Sieve (GNFS) ra đời. Khác với những người tiền nhiệm, GNFS không chỉ loanh quanh trong tập số nguyên thông thường. Nó thực hiện một cú nhảy vọt về tư duy: Chuyển bài toán từ tập số nguyên sang các trường số đại số (Algebraic Number Fields). Bằng cách xây dựng các đa thức phức tạp và làm việc trong không gian đa chiều của lý thuyết số, GNFS đã đạt được một kỳ tích: Biến tốc độ phân tích từ hàm mũ (exponential) – vốn cực chậm – thành hàm siêu đa thức dưới mức mũ (sub-exponential). Nói cách khác, GNFS đã thu hẹp khoảng cách giữa cái "không thể" và cái "có thể", trở thành thuật toán nhanh nhất thế giới hiện nay để bẻ khóa các mã khóa RSA có độ dài tổng quát.

Ý tưởng cốt lõi

Mọi thuật toán phân tích thừa số hiện đại, bao gồm cả GNFS, thực chất đều "đứng trên vai" một ý tưởng đơn giản của nhà toán học Pierre de Fermat từ thế kỷ 17.

Để phân tích một số lẻ $n$ thành nhân tử, mục tiêu của chúng ta là tìm hai số $x$ và $y$ sao cho:

Điều này tương đương với:

Nếu $x \not\equiv \pm y \pmod n$, thì $n$ phải chia sẻ các nhân tử chung với $(x - y)$ và $(x + y)$. Khi đó, ta chỉ cần dùng thuật toán Euclid để tính:

• Nếu $1 < d < n$, chúc mừng, bạn đã tìm được một nhân tử của $n$.

• Nếu $d=1$ hoặc $d=n$, đây là trường hợp 'xấu' ($x \equiv \pm y \pmod n$), ta phải chọn tập hợp các quan hệ khác từ bước Đại số tuyến tính để thử lại.

Trong một số ít trường hợp, ta tìm được $x \equiv y \pmod n$ hoặc $x \equiv -y \pmod n$. Khi đó $\gcd$ sẽ trả về $n$ hoặc $1$, không giúp ích gì cho việc phân tích. GNFS (và các thuật toán dạng Sieve) được thiết kế để tạo ra nhiều cặp $(x, y)$ khác nhau, đảm bảo xác suất thành công sau vài lần thử là cực lớn (thường là $> 50\%$ cho mỗi cặp).

Thuật toán Sàng Bình Phương (Quadratic Sieve - QS)

Trước khi đi vào thuật toán GNFS, chúng ta nên tìm hiểu thuật toán Sàng Bình Phương - QS vì đây chính là ý tưởng cốt lõi của GNFS. Mục tiêu của QS là tìm ra hai số $X,Y$ sao cho:

Vì nếu điều này xảy ra thì $X^2-Y^2=(X+Y)(X-Y)$ chia hết cho $n$ và ta có cơ hội cao tìm được nhân tử bằng cách tính $\gcd(X-Y, n)$.

Định nghĩa số mượt (Smooth number):

Một số nguyên $n$ được gọi là $B$-mượt nếu mọi ước nguyên tố $p$ của nó đều thỏa mãn $p \leq B$.

Ví dụ: Với ngưỡng $B = 10$:

• Số $48 = 2^4 \cdot 3^1$ là số 10-mượt (vì 2 và 3 đều < 10).

• Số $44 = 2^2 \cdot 11$ không là số 10-mượt (vì có ước 11 > 10).

Mục tiêu của chúng ta là tạo ra một số chính phương $Y^2$. Một số là chính phương khi và chỉ khi tất cả số mũ trong phân tích thừa số nguyên tố của nó đều là số chẵn. Nếu chúng ta có một tập hợp các số mượt, việc biến tích của chúng thành một số chính phương trở thành một bài toán giải hệ phương trình (Đại số tuyến tính) trên các số mũ modulo 2. Điều này dễ hơn rất nhiều so với việc mò mẫm ngẫu nhiên.

Có một quy luật bất biến trong lý thuyết số: Số càng nhỏ thì xác suất nó là số mượt càng cao. Hãy tưởng tượng bạn đang tìm các số mượt với ngưỡng $B=100$:

• Nếu bạn chọn một số ngẫu nhiên có 100 chữ số, xác suất để nó chỉ chứa các ước nguyên tố nhỏ hơn 100 là cực kỳ thấp (gần như bằng 0).

• Nếu bạn chọn một số chỉ có 10 chữ số, xác suất tìm thấy số mượt sẽ tăng lên hàng triệu lần.

Để thuật toán chạy nhanh, ta phải tìm cách tạo ra các số có độ lớn tối thiểu. Số càng nhỏ, ta càng mau chóng thu thập đủ "nguyên liệu" (các số mượt) để ghép thành bình phương $Y^2$.

Thuật toán QS:

Để tìm $X^2 \equiv Y^2 \pmod n$, ta cần $Y^2$ là kết quả của một tích các số mượt. QS chọn các số có dạng:

Lý do là vì:

• Tự động thỏa mãn điều kiện Modulo: Gọi $a = \lfloor \sqrt{n} \rfloor + x$. Ta luôn có $a^2 \equiv Q(x) \pmod n$. Vế trái ($a^2$) đã là một bình phương hoàn hảo. Ta chỉ cần "ép" vế phải $Q(x)$ thành bình phương nữa là xong.

• Tối ưu hóa độ lớn (The "Smallness" trick): Đây chính là lý do ta chọn $a \approx \sqrt{n}$.

  • Nếu chọn $a$ ngẫu nhiên, $Q(x)$ sẽ dễ lớn xấp xỉ $n$.

  • Nhưng vì $(\lfloor \sqrt{n} \rfloor + x)^2 \approx n$, nên khi trừ đi $n$, hiệu số $Q(x)$ sẽ rất nhỏ (chỉ xấp xỉ $2x\sqrt{n}$).

Sau khi đã có hàm "tạo số nhỏ" $Q(x)$, chúng ta sẽ thực hiện quy trình sau:

Bước 1: Thiết lập Cơ sở thừa số (Factor Base)

Chúng ta chọn một ngưỡng $B$ và tập hợp tất cả các số nguyên tố $p \leq B$. Đây chính là "lưới lọc" của chúng ta (Factor Base).

Bước 2: Giai đoạn Sàng (Sieving) – Đi tìm các số mượt

Sau khi đã có hàm $Q(x)$ và Factor Base (Cơ sở thừa số), chúng ta bắt đầu quy trình lọc tìm số mượt qua các tiểu bước sau:

• Trước khi bắt đầu "sàng", máy tính cần chuẩn bị một dải các ứng viên. Chúng ta xác định một khoảng giá trị của $x$ (ví dụ từ $x=1$ đến $x=1000$) và tính toán một loạt các giá trị $Q(x)$ tương ứng.Các giá trị này được nạp vào một mảng (array) trong bộ nhớ. Đây chính là "nguyên liệu thô" mà chúng ta sẽ đưa qua các lớp lưới lọc ở bước kế tiếp.

• Tiếp theo, thay vì lấy từng số $Q(x)$ trong mảng ra để chia thử (rất chậm), thuật toán tận dụng một tính chất toán học: Nếu $Q(x)$ chia hết cho một số nguyên tố $p$, thì các giá trị tiếp theo như $Q(x+p), Q(x+2p), \dots$ cũng sẽ chia hết cho $p$. Ý tưởng này gióng hệt như Sàng Erathostene.

• Quy trình thực hiện "Lọc" với mỗi số nguyên tố $p$ trong Factor Base:

  • Tìm vị trí $x$ đầu tiên mà $Q(x) \equiv 0 \pmod p$.

  • Nhảy: Cứ cách $p$ ô, ta lại thực hiện chia giá trị tại ô đó cho $p$ (chia cho đến khi không chia được nữa).

Sau bước lọc, máy tính sẽ trả về một danh sách các cặp quan hệ $(x_i, Q(x_i))$ thỏa mãn:

Trong đó $p_1, p_2, \dots$ đều nằm trong Factor Base mà bạn đã chọn ban đầu.

Bước 3: Chọn lọc để ghép bình phương

Mục tiêu của bước này là chọn ra một tập hợp các số mượt $Q(x_i)$sao cho khi nhân tất cả chúng lại, ta được một số mà tất cả các số mũ của các thừa số nguyên tố đều là số chẵn.

• Giả sử Factor Base của chúng ta là $\{2, 3, 5, 7\}$. Với mỗi số mượt tìm được, ta không quan tâm giá trị tuyệt đối của số mũ, ta chỉ quan tâm nó là Chẵn (0) hay Lẻ (1).

  • Ví dụ 1: $Q(x_1) = 2^3 \cdot 3^1 \cdot 5^0 \cdot 7^0 \implies$ Vector số mũ là $(3, 1, 0, 0)$.

    • Chuyển sang Modulo 2: $(3, 1, 0, 0) \pmod 2 = \mathbf{(1, 1, 0, 0)}$.

  • Ví dụ 2: $Q(x_2) = 2^1 \cdot 3^1 \cdot 5^2 \cdot 7^0 \implies$ Vector số mũ là $(1, 1, 2, 0)$.

    • Chuyển sang Modulo 2: $(1, 1, 2, 0) \pmod 2 = \mathbf{(1, 1, 0, 0)}$.

• Chúng ta xếp tất cả các vector nhị phân này thành các dòng của một ma trận:

  • Cột: Đại diện cho các số nguyên tố trong Factor Base.

  • Dòng: Đại diện cho từng số mượt $Q(x_i)$ mà ta nhặt được.

Bài toán bây giờ trở thành: Tìm một tổ hợp các dòng sao cho tổng của chúng (theo Modulo 2) bằng vector không $\mathbf{(0, 0, 0, 0)}$ vì tổng bằng 0 modulo 2 nghĩa là ở mỗi cột (mỗi số nguyên tố), tổng các số mũ là một số chẵn. Mà tích các số có số mũ chẵn thì chắc chắn là một Bình phương hoàn hảo.

Ví dụ: Giả sử sau bước Sàng, ta có 3 số mượt:

1. $Q(x_1) \to (1, 1, 0) \pmod 2$ (tương ứng $2^1 \cdot 3^1$)

2. $Q(x_2) \to (0, 1, 1) \pmod 2$ (tương ứng $3^1 \cdot 5^1$)

3. $Q(x_3) \to (1, 0, 1) \pmod 2$ (tương ứng $2^1 \cdot 5^1$)

Ma trận được tạo thành sẽ là:

Dễ dàng thấy rằng nếu ta cộng cả 3 dòng này lại:

Như vậy, nếu ta nhân $Q(x_1) \cdot Q(x_2) \cdot Q(x_3)$, ta sẽ được một bình phương hoàn hảo $Y^2$.

Với các số RSA lớn, ma trận này có thể lên tới hàng triệu dòng và cột. Việc giải bằng phương pháp khử Gauss (Gaussian Elimination) thông thường sẽ rất chậm. Thay vào đó, các siêu máy tính sử dụng các thuật toán tối ưu hơn cho Ma trận thưa (Sparse Matrix) như:

• Thuật toán Block Lanczos

• Thuật toán Wiedemann

Đây là những "con quái vật" về tốc độ, giúp tìm ra lời giải (tổ hợp các dòng) chỉ trong thời gian ngắn.

Bước 4: Tìm nhân tử (GCD)

Đây là bước chúng ta hiện thực hóa mục tiêu ban đầu: Biến đẳng thức modulo thành các nhân tử thực sự của $n$.

Từ kết quả của Bước 3, giả sử chúng ta tìm được tập hợp các chỉ số $S = \{i_1, i_2, \dots, i_k\}$ sao cho tích các dòng tương ứng trong ma trận bằng $0 \pmod 2$. Ta tính hai giá trị sau:

• Tính $X$: Là tích của các số $a_i$ (với $a_i = \lfloor \sqrt{n} \rfloor + x_i$) đã dùng để tạo ra các số mượt đó.

  $$X = \prod_{i \in S} a_i \pmod n$$

• Tính $Y$: Là căn bậc hai của tích các số mượt $Q(x_i)$. Vì tích này chắc chắn là bình phương hoàn hảo (do các số mũ đều chẵn), ta tính:

  $$Y = \sqrt{\prod_{i \in S} Q(x_i)} = \prod p^{e_j/2} \pmod n$$

  Với $e_j$ chính là tổng số mũ của số nguyên tố thứ $j$ trong tích của tất cả các số mượt mà chúng ta đã chọn.

Lúc này, theo đúng thiết lập của hàm $Q(x)$, chúng ta đã có:

Chúng ta không cần biết $n$ phân tích thành gì, chỉ cần dùng thuật toán Euclid để tìm ước chung lớn nhất:

• Nếu $1 < d < n$, thì $d$ chính là một nhân tử không tầm thường của $n$. Bài toán được giải.

• Nếu $d = 1$ hoặc $d = n$, nghĩa là chúng ta rơi vào trường hợp $X \equiv \pm Y \pmod n$ thì chúng ta quay lại Bước 3 để tìm tổ hợp khác.

Demo thuật toán QS

Tại sao cần GNFS?

Như bạn đã thấy ở các phần trước, hiệu quả của QS phụ thuộc vào độ lớn của hàm $Q(x)$.

• Trong QS, $Q(x) \approx \sqrt{n} = n^{1/2}$.

• Khi $n$ có 200 chữ số, $\sqrt{n}$ có tận 100 chữ số. Việc tìm một số mượt trong khoảng 100 chữ số vẫn là một thử thách quá lớn đối với máy tính hiện nay.

Từ QS đến GNFS

Cốt lõi của cả hai vẫn là đi tìm: $X^2 \equiv Y^2 \pmod n$. Nhưng sự khác biệt nằm ở chỗ chúng ta tìm các "số mượt" ở sư khác biệt về chiến thuật:

• Với QS: Bạn chỉ đi trên một con đường thẳng (số nguyên $\mathbb{Z}$). Bạn tìm số mượt $Q(x)$ có độ lớn xấp xỉ $\sqrt{n}$.

• Với GNFS: Bạn xây dựng một "cây cầu" nối giữa hai thế giới: Thế giới Hữu tỉ (số nguyên) và Thế giới Đại số (trường số phức tạp hơn). Nhờ cây cầu này, bạn chỉ phải tìm các số mượt có độ lớn xấp xỉ $n^{1/d}$ (với $d$ thường bằng 5 hoặc 6).

Ý tưởng của GNFS

Như bạn đã thấy ở phần Quadratic Sieve (QS), hiệu quả của thuật toán phụ thuộc rất lớn vào kích thước của hàm $Q(x)$. Trong QS, $Q(x) \approx \sqrt{n}$​. Khi $n$ có 200 chữ số, $\sqrt{n}$​ vẫn còn khoảng 100 chữ số – một con số quá lớn để dễ dàng tìm được các số mượt (smooth numbers).

GNFS giải quyết vấn đề này bằng một ý tưởng thông minh:
Thay vì làm việc trực tiếp với các số cỡ $\sqrt{n}$​, chúng ta dùng một đa thức bậc cao để “kéo” kích thước của các số cần sàng xuống chỉ còn khoảng $n^{1/d}$(với $d$ thường là 5 hoặc 6). Với $n$ 200 chữ số, $n^{1/5}$ chỉ còn khoảng 40 chữ số. Xác suất tìm thấy số mượt trong khoảng 40 chữ số cao hơn hàng tỷ lần so với 100 chữ số. Đó chính là lý do GNFS trở thành vua của việc phân tích thừa số.

Xây dựng hai thế giới song song

Để làm được điều này, GNFS tạo ra hai thế giới hoạt động cùng lúc:

• Thế giới hữu tỉ (Rational side): Chính là tập hợp các số nguyên $\mathbb{Z}$ quen thuộc.

• Thế giới đại số (Algebraic side): Vành số nguyên $\mathbb{Z}[\alpha]$, trong đó $\alpha$ là một nghiệm của đa thức $f(x)$ mà chúng ta chọn.

Hai thế giới này được nối với nhau bởi một ánh xạ đồng cấu $\phi$:

Quy tắc cực kỳ đơn giản: Ở đâu có $\alpha$, hãy thay bằng $m$ (một số nguyên ta chọn). Ví dụ: $\phi(a - b\alpha) = a - bm \pmod{n}$

Tính chất quan trọng nhất của $\phi$ là bảo toàn phép nhân:

Nhờ đó, mọi phép tính phức tạp ở thế giới đại số đều có thể “nhảy” về thế giới hữu tỉ một cách nhất quán.

Chọn đa thức $f(x)$và số $m$ (Base-$m$ method)

Chúng ta chọn một đa thức $f(x)$ bậc $d$ (thường $d = 5$hoặc $6$) có hệ số nhỏ, sao cho tồn tại số nguyên $m$ thỏa mãn:

Cách chọn phổ biến nhất (Base-$m$):

• Chọn $m \approx n^{1/(d+1)}$

• Viết $n$ dưới dạng cơ số $m$:

  $$n = c_d m^d + c_{d-1} m^{d-1} + \dots + c_0$$

• Khi đó đa thức chính là:

  $$f(x) = c_d x^d + c_{d-1} x^{d-1} + \dots + c_0$$

Lúc này $f(m) = n$, nên $f(m) \equiv 0 \pmod{n}$, và $\alpha$ là nghiệm của $f(x)$, tức $f(\alpha) = 0$.

Phía hữu tỉ (Rational Side) – Giống QS

Ta xét các số nguyên $a−bm$. Mục tiêu là tìm một tập hợp $S$ các cặp $(a,b)$ sao cho tích của chúng là một bình phương:

Đây chính là bài toán sàng số mượt quen thuộc trong QS.

Phía đại số (Algebraic Side)

Ở đây ta xét các phần tử $a-b\alpha \in \mathbb{Z}[\alpha]$. Ta muốn tích của chúng cũng là một bình phương trong $\mathbb Z[\alpha]$:

Vấn đề:$a - b\alpha$ không phải số nguyên thông thường, nên ta không thể factor trực tiếp như trong $\mathbb{Z}$.

Giải pháp: Sử dụng Norm và Prime ideals.

Norm của $\beta = a + b\alpha$ là một số nguyên được định nghĩa bằng:

Ví dụ với $f(x) = x^2 - 9$, và $d=2$ thì:

Norm có tính chất nhân rất đẹp: $N(\beta \cdot \gamma) = N(\beta) \cdot N(\gamma)$. Nếu $N(a - b\alpha)$ là số mượt (chỉ gồm thừa số nguyên tố nhỏ), thì $a - b\alpha$ được coi là “đủ mịn” ở phía đại số.

Prime Ideals

Trong $\mathbb{Z}[\alpha]$, khái niệm “số nguyên tố” được thay bằng prime ideal $\mathfrak{p}$. Mỗi prime ideal nằm “trên” một số nguyên tố $p$ trong $\mathbb{Z}$ và có norm $N(\mathfrak{p})$ (thường là $p$ hoặc $p^k$).

Analog dễ hình dung:

• Trong $\mathbb{Z}$: factor base là tập các số nguyên tố nhỏ.

• Trong $\mathbb{Z}[\alpha]$: factor base algebraic là tập các prime ideals có norm nhỏ.

Khi $N(a - b\alpha)$ factor hoàn toàn thành các số nguyên tố nhỏ, ta có thể ánh xạ ngược lại thành tích của các prime ideals nhỏ.

Tại sao phải dùng prime ideals?

Vì trong vành $\mathbb Z[\alpha]$, ta có định lý phân tích duy nhất the prime ideal. Nghĩa là mọi phần tử không-zero đều có thể phân tích thành tích của các prime ideal một cách duy nhất (tính đến đơn vị). Do đó, thay vì nói “$a - b\alpha$ được phân tích thành thừa số nào”, ta nói: "$a-b\alpha$ thuosc tích của một số prime ideal có norm nhỏ".

Ví dụ với $n=91, f(x)=x^2-9$, khi ta tính $N(4-\alpha)=7$, số 7 trên phía hữu tỉ tương ứng với một (hoặc vài) prime ideals $\mathfrak{p}$nằm trên $p=7$ ở phía đại số, với $N(\mathfrak{p}) = 7$. Tương tự, khi $N(-18 - \alpha) = 315 = 3^2 \cdot 5 \cdot 7$, ta ánh xạ thành tích của các lý tưởng nguyên tố tương ứng với 3, 5, 7.

Nói chung, vài trò của prime ideals ho phép chúng ta xây dựng một “từ điển” chung giữa hai thế giới:

• Phía hữu tỉ: dùng số nguyên tố thông thường.

• Phía đại số: dùng lý tưởng nguyên tố có norm nhỏ.

Khi thu thập đủ relations, ta sẽ có một ma trận chứa cả hai loại “thừa số” này. Bước đại số tuyến tính sau đó tìm một tổ hợp tuyến tính (mod 2) sao cho tổng số mũ của mọi số nguyên tố và mọi lý tưởng nguyên tố đều chẵn → cả hai phía đều trở thành bình phương.

Tóm tắt ý tưởng then chốt:
Ta sàng tìm các cặp $(a, b)$ sao cho:

• Phía rational: $a - bm$ là smooth theo số nguyên tố.

• Phía algebraic: $N(a - b\alpha)$ là smooth theo prime ideals.

Khi thu thập đủ nhiều cặp như vậy, bước đại số tuyến tính sẽ tìm một tổ hợp (mod 2) làm cho tích ở cả hai phía đều trở thành bình phương.

Kết nối hai phía → Phá RSA

Nhờ tính đồng cấu của $\phi$, khi cả hai phía đều là bình phương, ta có:

Với $X \neq \pm Y \pmod{n}$. Lúc này $\gcd(X-Y,n), \gcd(X+Y,n)$ sẽ cho ta hai thừa số không tầm thường của $n$. Đó chính là cách GNFS “phá” RSA.

Quy trình 4 bước của thuật toán GNFS

Bước 1: Chọn đa thức (Polynomial Selection)

Trong QS, hàm $Q(x)$ rất đơn giản. Trong GNFS, đây là bước quan trọng nhất:

• Ta chọn một đa thức $f(x)$ bậc $d$ và một số $m$ sao cho $f(m) \equiv 0 \pmod n$.

• Việc này thiết lập nên Tính Đồng cấu: Ở đâu có nghiệm $\alpha$ của đa thức, ta có thể thay bằng số nguyên $m$ khi xét modulo $n$.

Bước 2: Sàng (Sieving) - Từ đường thẳng lên mặt phẳng

• QS: Sàng trên một dãy số $x$ để tìm $Q(x)$ mượt.

• GNFS: Sàng trên một mặt phẳng tọa độ $(a, b)$. Chúng ta đi tìm các cặp $(a, b)$ sao cho cả hai bên cầu đều mượt:

  • Phía Hữu tỉ: $(a - bm)$ là số mượt.

  • Phía Đại số: $(a - b\alpha)$ là "số mượt" (trong trường đại số).

Bước 3: Đại số tuyến tính (Linear Algebra)

• QS: Ma trận chỉ chứa các số nguyên tố nhỏ.

• GNFS: Ma trận phức tạp hơn gấp đôi vì nó phải chứa cả các số nguyên tố thường (hữu tỉ) và các "lý tưởng nguyên tố" (phía đại số).

• Mục tiêu: Vẫn là tìm một tổ hợp các cặp $(a, b)$ sao cho tích của chúng tạo ra bình phương ở cả hai phía.

Bước 4: Khai căn và GCD (Square Root & GCD)

• QS: Khai căn tích các số nguyên (rất dễ).

• GNFS: Phía hữu tỉ thì dễ, nhưng phía đại số bạn phải khai căn một tích các phần tử $(a - b\alpha)$. Vì tích này cực kỳ lớn, ta phải dùng các thuật toán chuyên sâu để tìm căn bậc hai $\gamma$ mà không cần nhân trực tiếp.

• Kết thúc: Khi đã có $X$ (hữu tỉ) và $Y = \phi(\gamma)$ (đại số), ta tính:

  $$\text{Factor} = \gcd(X - Y, n)$$

Ví dụ thực tiễn

Gia sử ta muốn factor $n=91 (=7 \times 13)$ với factor base $\{2,3,5,7,11,13\}$

Bước 1: Polynomial selection

• Chọn $m=10$

• Chọn $f(x) = x^2 - 9$ vì $f(10) = 100 - 9 = 91 \equiv 0 \pmod {91}$

Bước 2: Sieving

Giờ ta xét các cặp $(a,b)$ ví dụ: $(a,b) = (11,1)$ ta có:

• $a-bm = 11-10=1$ smooth!

• Ta có $f(x) = x^2 - 9$ và $\alpha$ là nghiệm của $f(x)$ nên $\alpha^2 = 9$. Vậy $Norm(a - b\alpha) = a^2 - b^2 \times 9 = 112 = 2^4 \times 7$ smooth!

Vậy ta có 1 relation hợp lệ: $(11,1) \to (1,112)$

Bước 3: Linear algebra

Giả sử sau khi tìm kiếm ta tìm thêm được 4 relation sau (cả rational và algebraic đều smooth):

Sau khi giải hệ tuyến tính mod 2 (Gaussian elimination hoặc Block Lanczos trong thực tế), ta tìm được một dependency: sử dụng Relation 2, 3, 4 và 5. Kết quả là:

• Tích các giá trị rational side là một bình phương $X^2$.

• Tích các Norm (algebraic side) là một bình phương $\gamma^2$ trong vành $\mathbb{Z}[\alpha]$

Bước 4: Từ dependency trên ta tính

• $X = \sqrt{\text{tích rational side}}$ (phía hữu tỉ).

• $\gamma = \sqrt{\text{tích algebraic side}}$​ (phía đại số).

• $Y = \phi(\gamma)$ (ánh xạ đồng cấu về $\mathbb{Z}/n\mathbb{Z}$).

Kết quả thu được trong ví dụ này:

• $X = 37$

• $Y = 2$

Kiểm tra:

Suy ra $X^2 \equiv Y^2 \pmod{91}$ và $X \not\equiv \pm Y \pmod {91}$.

Tính gcd:

Vậy $91 = 7 \times 13$. Thuật toán GNFS thành công!

Để dễ hình dung, bạn có thể chơi với demo tiếp theo nhé.

Demo cho GNFS

Bảng so sánh các bước giữa QS và GGFS

Cuối cùng, hãy cùng nhìn lại bảng so sánh các bước giữa 2 thuật toán QS và GNFS