Thuật toán General Number Field Sieve (GNFS)

Sàng Trường Số Tổng Quát — cơ sở lý thuyết, phân tích toán học, minh hoạ trực quan và triển khai mã nguồn C

Sự phát triển của mật mã học hiện đại, đặc biệt là hệ mật mã khoá công khai như thuật toán RSA, phụ thuộc hoàn toàn vào tính khó của Bài toán Phân tích Số nguyên (Integer Factorization Problem — IFP). Đối với các hợp số lớn không có dạng đặc biệt và vượt quá ngưỡng 100 chữ số thập phân, thuật toán Sàng Trường Số Tổng Quát (General Number Field Sieve — GNFS) được chứng minh là phương pháp cổ điển hiệu quả và mạnh mẽ nhất từng được biết đến.

Bài viết này trình bày một phân tích toàn diện về GNFS: từ nền tảng lý thuyết đại số trừu tượng, quá trình kiến tạo đa thức và hình học ma trận, cho đến mô phỏng trực quan bằng HTML5 Canvas, và cuối cùng là phương pháp triển khai kiến trúc phần mềm bằng ngôn ngữ C.

1. Nền tảng lý thuyết

1.1. Bối cảnh lịch sử và độ phức tạp

GNFS là sự tiến hoá mang tính bước ngoặt từ thuật toán Sàng Trường Số Đặc Biệt (Special Number Field Sieve — SNFS), vốn được John Pollard đề xuất năm 1988 nhằm phân tích các số có dạng đại số đặc biệt, điển hình như các số Fermat $c_1 r^t + c_2 s^u$. Trong khi SNFS có giới hạn ứng dụng hẹp, cấu trúc của nó đã tạo tiền đề để các nhà toán học như Arjen K. Lenstra, H. W. Lenstra Jr., Mark Manasse và John Pollard mở rộng thành GNFS, cho phép phân tích bất kỳ số nguyên $n$ nào (ngoại trừ số nguyên tố hoặc luỹ thừa của một số nguyên tố).

Sức mạnh đột phá của GNFS nằm ở khả năng tìm kiếm các "số trơn" (smooth numbers) — những số chỉ chứa các ước nguyên tố nhỏ. Nhờ việc sử dụng các trường số đại số (algebraic number fields) thay vì chỉ làm việc trên vành số nguyên thông thường, GNFS đạt được độ phức tạp thời gian tiệm cận dưới mức hàm mũ (sub-exponential), thường được biểu diễn qua ký hiệu tiệm cận $L$:

Đối với GNFS, độ phức tạp được xác định tại $\alpha = 1/3$, cụ thể là $L_n[1/3, (64/9)^{1/3}]$, tương đương hằng số $c \approx 1.923$. So với Sàng Bậc Hai (Quadratic Sieve) có độ phức tạp $L_n[1/2, 1]$, GNFS ban đầu chạy chậm hơn với số nhỏ, nhưng bắt đầu vượt trội hoàn toàn khi số chữ số của $n$ vượt ngưỡng 110 đến 130 chữ số thập phân. Đây là công cụ chính phá vỡ các kỷ lục phân tích RSA, từ RSA-155 (512-bit) năm 1999 cho đến RSA-768 và lớn hơn.

1.2. Nguyên lý Đồng dư Bình phương

Mục tiêu cốt lõi của GNFS, tương tự họ thuật toán phân tích cổ điển, là khai thác nguyên lý đồng dư bình phương. Thuật toán cố gắng tìm ra hai số nguyên $x$ và $y$ sao cho:

Khi đó $x^2 - y^2 = (x - y)(x + y)$ chia hết cho $n$, nhưng $n$ không thể chia hết hoàn toàn cho riêng $(x-y)$ hoặc riêng $(x+y)$. Bằng thuật toán Euclid, $\gcd(x - y, n)$ hoặc $\gcd(x + y, n)$ sẽ trả về một thừa số nguyên tố thực sự của $n$.

Điểm khác biệt của GNFS là cách tạo ra $x$ và $y$. Thay vì tìm kiếm trực tiếp số trơn trong vành số nguyên $\mathbb{Z}$, thuật toán xây dựng một vành đại số $\mathbb{Z}[\alpha]$ và ánh xạ giá trị sang trường số nguyên modulo $n$ thông qua một đồng hình vành (ring homomorphism).

1.3. Cấu trúc Đại số của Đồng hình Vành

GNFS yêu cầu chọn hai đa thức tối giản $f(x)$ và $g(x)$ có hệ số nguyên, chia sẻ chung một nghiệm $m$ modulo $n$. Theo quy chuẩn thực hành, $g(x)$ thường là đa thức tuyến tính $g(x) = x - m$, còn $f(x)$ là đa thức bậc $d$ (thường từ 4 đến 6 với các số khổng lồ). Ký hiệu $\alpha$ là một nghiệm phức của $f(x)$ (tức $f(\alpha) = 0$), sinh ra trường số đại số $\mathbb{Q}(\alpha)$ với vành con $\mathbb{Z}[\alpha]$.

Vì $m$ và $\alpha$ đều là nghiệm của $f(x)$, tồn tại một đồng hình vành $\phi: \mathbb{Z}[\alpha] \to \mathbb{Z}/n\mathbb{Z}$ xác định bởi $\phi(\alpha) = m \pmod n$. Bản chất của GNFS là tìm tập các cặp số nguyên $(a, b)$ đồng nguyên tố sao cho:

• Tích các số $(a - b\alpha)$ là một bình phương trong $\mathbb{Z}[\alpha]$;
• Tích các giá trị hữu tỉ $(a - bm)$ là một bình phương trong $\mathbb{Z}$.

Nhờ tính bảo toàn phép nhân của $\phi$, bình phương trong vành đại số được ánh xạ thành bình phương trong $\mathbb{Z}/n\mathbb{Z}$, thoả mãn điều kiện $x^2 \equiv y^2 \pmod n$.

2. Bốn giai đoạn vận hành

Toàn bộ quy trình được chia thành bốn giai đoạn tách biệt. Sự phân tách này phục vụ cho lập trình hệ thống song song, khi mỗi giai đoạn đòi hỏi một loại tài nguyên phần cứng khác nhau.

2.1. Lựa chọn Đa thức

Thuật toán cơ sở là khai triển cơ số $m$ (base-$m$ expansion): chọn $m \approx \lfloor n^{1/d} \rfloor$ và biểu diễn $n$ theo cơ số $m$:

Đa thức thu được là $f(x) = \sum_{i=0}^d c_i x^i$, đảm bảo $f(m) = n \equiv 0 \pmod n$. Chất lượng đa thức được tối ưu qua hai tiêu chí: Thuộc tính kích thước (giá trị của đa thức thuần nhất $F(a, b) = b^d f(a/b)$ phải nhỏ, được tối ưu qua độ nghiêng skewness $s$ để giảm chuẩn $L_2$), và Thuộc tính nghiệm (đa thức có nhiều nghiệm modulo các nguyên tố nhỏ). Các nhà nghiên cứu dùng hàm Murphy's $E$ qua hàm phân phối Dickman-de Bruijn $\rho(u)$ để chọn bộ đa thức ưu việt nhất; thuật toán Kleinjung (2006) là một cải tiến nổi bật.

2.2. Sàng Trường Số (Sieving)

Mục đích là thu thập hàng triệu cặp $(a, b)$ đồng nguyên tố ($\gcd(a,b)=1$) sao cho cả hai giá trị sau đều trơn so với các ranh giới định trước:

• Phía hữu tỉ: $|a - bm|$ phân tích hoàn toàn trên Cơ sở nhân tử hữu tỉ $\mathcal{F}_R$ (các nguyên tố $p < B_1$).
• Phía đại số: Chuẩn $|N(a - b\alpha)| = |b^d f(a/b)|$ phân tích hoàn toàn trên Cơ sở nhân tử đại số $\mathcal{F}_A$ (các cặp $(p, r)$ với $p \le B_2$ và $f(r) \equiv 0 \pmod p$).

Đây là giai đoạn tiêu tốn tài nguyên nhất. Thay vì chia thử (trial division), GNFS dùng Sàng Dòng (Line Sieving — cố định $b$, quét $a$, cộng dồn $\log(p)$) hoặc Sàng Mạng Lưới (Lattice Sieving — thuật toán Jens Franke, tối ưu CPU cache). Biến thể Large Prime Variation chấp nhận các cặp chứa một, hai, ba số nguyên tố lớn, rồi ghép nối qua thuật toán union-find để tạo thành chu kỳ (cycle) hợp lệ.

2.3. Bộ lọc và Đại số Tuyến tính

Sau khi thu đủ quan hệ, GNFS xây dựng hệ phương trình trên trường hữu hạn $\mathbb{F}_2$. Quá trình Filtering loại bỏ các "singleton" (nguyên tố chỉ xuất hiện một lần), giảm kích thước ma trận. Mỗi quan hệ thành một cột trong ma trận thưa; giá trị ô $(i, j)$ là $1$ nếu số mũ của nguyên tố $i$ trong quan hệ $j$ là lẻ. Bài toán là tìm không gian null (nullspace) — tổ hợp tuyến tính các cột có tổng modulo 2 bằng $\mathbf{0}$.

Ký tự Bậc hai (Quadratic Characters): ngay cả khi tổ hợp làm mọi lý tưởng nguyên tố có bậc chẵn, điều đó chỉ đảm bảo tích là một lý tưởng bình phương, chưa chắc là bình phương của một phần tử đại số thực sự (do nhóm lớp và các đơn vị). L. Adleman đề xuất bổ sung Ký tự Bậc hai: tính Ký hiệu Legendre của $(a - b\alpha)$ với các lý tưởng ngoài cơ sở nhân tử, thêm vào ma trận $\mathbb{F}_2$ như các hàng bổ sung.

Giải ma trận hàng chục triệu hàng là bất khả thi với Khử Gauss (chi phí $\mathcal{O}(N^3)$). Thay vào đó, thuật toán Block Lanczos hoặc Block Wiedemann — các phương pháp lặp dựa trên phép nhân ma trận-vectơ — cho phép xử lý ma trận thưa trong thời gian $\mathcal{O}(N^{2+\epsilon})$ và bộ nhớ tuyến tính $\mathcal{O}(N)$.

2.4. Rút Căn Bậc Hai Đại số

Nullspace chỉ định tập con $S$ các cặp $(a, b)$ sao cho tích của chúng là bình phương. Ta cần tính:

Tính $X$ khá đơn giản vì đã biết phân tích thừa số của $\prod (a-bm)$ — chỉ cần lấy nửa số mũ mỗi thừa số rồi nhân modulo $n$. Nhưng rút căn phía đại số cực kỳ khó: giá trị $T(\alpha)$ có độ dài lên đến hàng triệu bit. Các phương pháp gồm: nâng p-adic (bổ đề Hensel), thuật toán Montgomery (phổ biến nhất, không cần nguyên tố trơ), và thuật toán Couveignes.

Khi đã có $X$ và $Y$, kiểm tra $X \equiv \pm Y \pmod n$. Nếu không, $\gcd(X-Y, n)$ ngay lập tức giải quyết bài toán IFP, phá vỡ khoá RSA.

3. Mô phỏng tương tác: Giai đoạn Sàng

Mô hình dưới đây minh hoạ nguyên lý cốt lõi của Giai đoạn Sàng trên mặt phẳng $(a, b)$. Trục ngang là giá trị $a$, trục dọc là $b$. Thuật toán quét tuần tự, đánh giá đồng thời phía hữu tỉ $|a - bm|$ và phía đại số $F(a,b)$. Các ô xanh lá là các cặp trơn hợp lệ (relation) — mỗi ô sẽ trở thành một vector nạp vào ma trận $\mathbb{F}_2$.

4. Mã nguồn C: Rational Sieve

Các hệ thống GNFS thực thụ (như msieve của Jason Papadopoulos hay CADO-NFS) là những thư viện khổng lồ kết hợp hàng chục nghìn dòng C, assembly và thư viện đa độ chính xác GMP. Dưới đây là phiên bản rút gọn của Thuật toán Sàng Hữu Tỉ — cấu trúc toán học tương đồng với GNFS nhưng giới hạn bậc đa thức $d=1$, đủ để minh hoạ quản lý mảng, tính số trơn và ma trận $\mathbb{F}_2$.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define MAX_PRIMES 100
#define SIEVE_BOUND 5000

/*
 * Cấu trúc đại diện cho một "Mối quan hệ" (Relation).
 * z là giá trị khởi điểm; exp_z và exp_zn lưu số mũ của
 * từng nguyên tố trong cơ sở nhân tử.
 */
typedef struct {
    int z;
    int exp_z[MAX_PRIMES];
    int exp_zn[MAX_PRIMES];
} Relation;

/* Thuật toán Euclid tính Ước chung lớn nhất */
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

/*
 * GIAI ĐOẠN 1: Xây dựng Cơ sở nhân tử bằng Sàng Eratosthenes.
 * Độ phức tạp O(n log log n).
 */
int generate_factor_base(int bound, int primes[]) {
    bool* is_prime = (bool*)malloc((bound + 1) * sizeof(bool));
    for (int i = 0; i <= bound; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    for (int p = 2; p * p <= bound; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= bound; i += p) is_prime[i] = false;
        }
    }
    int count = 0;
    for (int i = 2; i <= bound; i++) {
        if (is_prime[i]) primes[count++] = i;
    }
    free(is_prime);
    return count;
}

/*
 * Kiểm tra độ trơn qua chia liên tiếp (Trial Division).
 * GNFS thực tế dùng Array of Logarithms để tăng tốc.
 */
bool factorize_smooth(long long n, int primes[], int num_primes, int exponents[]) {
    long long temp = n;
    for (int i = 0; i < num_primes; i++) {
        exponents[i] = 0;
        while (temp % primes[i] == 0) {
            exponents[i]++;
            temp /= primes[i];
        }
    }
    return temp == 1; // Chỉ thành công khi phân tích xong về 1
}

/* Hàm chính: Phân tích bằng Rational Sieve */
void rational_sieve(long long N, int B) {
    printf("[*] Khoi dong Sang Huu Ti phan tich N=%lld, Gioi han B=%d\n", N, B);
    int primes[MAX_PRIMES];
    int k = generate_factor_base(B, primes);
    printf("[+] Kich thuoc Co so nhan tu: %d nguyen to.\n", k);

    Relation* rel_matrix = (Relation*)malloc(SIEVE_BOUND * sizeof(Relation));
    int total_relations = 0;

    /* GIAI ĐOẠN 2: SIEVING — quét chuỗi z, đánh giá z và z+N */
    for (int z = 2; z < SIEVE_BOUND; z++) {
        int exp_z[MAX_PRIMES] = {0};
        int exp_zn[MAX_PRIMES] = {0};
        if (factorize_smooth(z, primes, k, exp_z)) {
            if (factorize_smooth(z + N, primes, k, exp_zn)) {
                rel_matrix[total_relations].z = z;
                for (int i = 0; i < k; i++) {
                    rel_matrix[total_relations].exp_z[i] = exp_z[i];
                    rel_matrix[total_relations].exp_zn[i] = exp_zn[i];
                }
                total_relations++;
            }
        }
    }
    printf("[+] Hoan tat sang loc. Phat hien %d relations.\n", total_relations);

    if (total_relations < k + 2) {
        printf("[-] Loi: Can toi thieu %d relations (K+2) de giai Nullspace.\n", k + 2);
        free(rel_matrix);
        return;
    }

    /* GIAI ĐOẠN 3 & 4: Kết hợp 2 relations sinh bình phương (minh hoạ) */
    bool success = false;
    for (int i = 0; i < total_relations - 1 && !success; i++) {
        for (int j = i + 1; j < total_relations && !success; j++) {
            bool isValidSquare = true;
            for (int p = 0; p < k; p++) {
                int sum_z  = rel_matrix[i].exp_z[p]  + rel_matrix[j].exp_z[p];
                int sum_zn = rel_matrix[i].exp_zn[p] + rel_matrix[j].exp_zn[p];
                if (sum_z % 2 != 0 || sum_zn % 2 != 0) { isValidSquare = false; break; }
            }
            if (isValidSquare) {
                long long X = 1, Y = 1;
                for (int p = 0; p < k; p++) {
                    int eX = (rel_matrix[i].exp_z[p]  + rel_matrix[j].exp_z[p])  / 2;
                    int eY = (rel_matrix[i].exp_zn[p] + rel_matrix[j].exp_zn[p]) / 2;
                    X = (X * (long long)pow(primes[p], eX)) % N;
                    Y = (Y * (long long)pow(primes[p], eY)) % N;
                }
                long long f1 = gcd(llabs(X - Y), N);
                long long f2 = gcd(X + Y, N);
                if (f1 > 1 && f1 < N) {
                    printf("[!] THANH CONG: Nhan tu p=%lld => %lld = %lld * %lld\n", f1, N, f1, N / f1);
                    success = true;
                } else if (f2 > 1 && f2 < N) {
                    printf("[!] THANH CONG: Nhan tu q=%lld => %lld = %lld * %lld\n", f2, N, f2, N / f2);
                    success = true;
                }
            }
        }
    }
    if (!success) {
        printf("[-] Chi tim thay to hop tam thuong. Can Gaussian Elimination day du.\n");
    }
    free(rel_matrix);
}

int main() {
    long long N_target = 187; // Semiprime = 11 * 17
    int Bound = 15;
    rational_sieve(N_target, Bound);
    return 0;
}

5. Từ minh hoạ đến kiến trúc GNFS chuẩn

Mã C trên nắm giữ đặc tính toán học của giai đoạn sàng, nhưng một hệ thống chuẩn xác (msieve, CADO-NFS của Jens Franke và Thorsten Kleinjung) đòi hỏi hàng loạt biến đổi kỹ thuật:

• → Sàng Logarit thay vì chia modulo: lệnh chia trên CPU rất tốn xung nhịp. Hệ thống thực dùng một mảng byte (nằm trọn trong L1 Cache), cộng trừ xấp xỉ $\log(p)$ thay vì chia. Ô nào vượt ngưỡng mới được gọi Trial Division để xác nhận.
• → Xử lý đa độ chính xác: kiểu long long chỉ đủ 64-bit (<20 chữ số). Với RSA-155 (512-bit) hay RSA-768 (232 chữ số), mọi biến $N, a, b, c_i$ phải đóng gói vào cấu trúc mpz_t của thư viện GMP.
• → Tổ chức ma trận & Block Lanczos: ma trận thưa $\mathbb{F}_2$ được nén dạng Compressed Sparse Row; kỹ thuật bit-packing đóng gói 64–256 phần tử vào một thanh ghi, thực thi qua cổng logic XOR (^) và AND (&).
• → Cơ sở Ký tự Bậc hai $\mathcal{Q}$: tập các cặp $(p, r)$ với nguyên tố cực lớn, không tham gia sàng, chỉ tạo các cột ma trận từ Ký hiệu Legendre nhằm đảm bảo tính nguyên vẹn của căn bậc hai phía đại số.

6. Kết luận

General Number Field Sieve không chỉ chứng minh vẻ đẹp trừu tượng của Lý thuyết số (từ đại số giao hoán, phân rã đa thức, đến nhóm lớp và lý tưởng nguyên tố), mà còn phản chiếu đỉnh cao của kỹ thuật phần mềm hiệu suất cao. Hiệu năng của GNFS đến từ cả sự vượt trội tiệm cận lẫn hàng chục nghìn giờ tối ưu hoá vi mô: lợi dụng cache vi xử lý, sàng logarit mạng lưới, và Block Lanczos.

GNFS đã, đang, và sẽ tiếp tục là "nhà vô địch cổ điển" trong sứ mệnh thách thức các hệ mật mã dựa trên phân tích số nguyên — cho tới khi các máy tính lượng tử thực sự trưởng thành.