Thuật toán Pollard's Rho

Phân tích một số nguyên ra thừa số nguyên tố

1. Giới thiệu

Thuật toán Pollard's rho là một thuật toán dùng để phân tích một số nguyên ra thừa số nguyên tố, được phát minh bởi John Pollard vào năm 1975. Nó đặc biệt hiệu quả trong việc tìm các ước số nguyên tố nhỏ của một hợp số lớn.

Thời gian chạy dự kiến của thuật toán tỷ lệ thuận với căn bậc hai của ước nguyên tố nhỏ nhất của số cần phân tích. Mặc dù không phải là thuật toán phân tích nhanh nhất hiện nay (như Quadratic Sieve hay General Number Field Sieve), nhưng Pollard's rho cực kỳ hữu ích trong thực tế vì tính đơn giản và hiệu quả cao hơn nhiều so với phương pháp chia thử (trial division) truyền thống. Khả năng nổi bật nhất của thuật toán này là nó sử dụng rất ít bộ nhớ.

Thuật toán đã chứng minh được sức mạnh của mình khi Pollard và Brent sử dụng nó để phân tích số Fermat thứ tám ($F_8 = 2^{256} + 1$).

2. Ý tưởng chính

Thuật toán Pollard's rho là sự kết hợp thông minh giữa hai khái niệm:

Nghịch lý ngày sinh nhật (Birthday paradox): Xác suất để hai số $x$ và $y$ được chọn ngẫu nhiên đồng dư theo modulo $p$ (nghĩa là $x \equiv y \pmod p$ hay $p$ là ước của $|x - y|$) cao hơn nhiều so với dự đoán thông thường.
Thuật toán phát hiện chu trình của Floyd (Floyd's cycle-finding algorithm): Còn được gọi là thuật toán "Rùa và Thỏ", dùng để phát hiện chu trình trong một chuỗi sinh bằng hàm ngẫu nhiên giả mà không cần lưu trữ toàn bộ chuỗi.

Cách thức hoạt động

Giả sử ta cần phân tích số $N$. Chúng ta tìm một ước số $p$ của $N$ ($1 < p < N$). Thay vì tìm trực tiếp nghiệm, thuật toán định nghĩa một hàm đa thức ngẫu nhiên giả, thường là:

$$f(x) = (x^2 + c) \pmod N$$

(với $c$ là một hằng số ngẫu nhiên, thường chọn $c = 1$). Bắt đầu với một giá trị $x_0$ ban đầu (ví dụ $x_0 = 2$), ta tạo ra một dãy số:

$$x_1 = f(x_0), \quad x_2 = f(x_1), \quad x_3 = f(x_2), \quad \dots$$

Vì tập các số theo modulo $N$ là hữu hạn, dãy này chắc chắn sẽ rơi vào một chu trình (lặp lại các giá trị). Khi biểu diễn trên đồ thị có hướng, dãy này có hình dáng giống chữ cái Hy Lạp $\rho$ (rho), gồm một phần đuôi và một vòng lặp, giải thích cho tên gọi của thuật toán.

Để phát hiện chu trình, ta duy trì hai biến (Rùa và Thỏ):

🐢 Rùa ($x$) di chuyển một bước: $x = f(x)$
🐇 Thỏ ($y$) di chuyển hai bước: $y = f(f(y))$

Ở mỗi bước, ta tính ước chung lớn nhất (GCD):

$$d = \gcd(|x - y|, N)$$

Nếu $1 < d < N$: Thuật toán thành công, $d$ chính là một ước không tầm thường của $N$.
Nếu $d = 1$: Tiếp tục vòng lặp.
Nếu $d = N$: Thuật toán thất bại, hàm $f(x)$ đã sinh ra một chu trình có độ dài là bội của $N$ mà không tìm được $p$. Ta cần đổi giá trị bắt đầu $x_0$ hoặc hằng số $c$ và thử lại.

Mô phỏng tương tác

Nhấn Bước hoặc Tự động để chạy thuật toán và xem dãy số cuộn dần thành hình chữ ρ. Khi tìm được ước số, các đỉnh cùng số dư sẽ được gộp lại. Bạn có thể kéo thả các đỉnh.

Số N (cần phân tích)

Start (x₀)

Hệ số (c)

Tốc độ:

Vòng lặp (k): 0

🐢 Rùa (x): 2

🐇 Thỏ (y): 2

|x - y|: 0

GCD: 1

3. Mã nguồn C minh hoạ

Dưới đây là một ví dụ mã nguồn C cơ bản triển khai thuật toán Pollard's rho, sử dụng kiểu long long cho các số tối đa 64-bit. Để tránh tràn số khi nhân hai số 64-bit, mã nguồn sử dụng hàm mul_mod.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Hàm tính Ước chung lớn nhất (GCD)
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Hàm nhân (a * b) % m tránh tràn số (overflow) cho số nguyên lớn
long long mul_mod(long long a, long long b, long long m) {
    long long res = 0;
    a = a % m;
    while (b > 0) {
        if (b % 2 == 1) res = (res + a) % m;
        a = (a * 2) % m;
        b /= 2;
    }
    return res % m;
}

// Hàm trị tuyệt đối
long long absolute(long long x) {
    return x < 0 ? -x : x;
}

// Thuật toán Pollard's rho
long long pollard_rho(long long n) {
    // Nếu n là số chẵn, 2 là một ước số
    if (n % 2 == 0) return 2;

    // Khởi tạo các giá trị ngẫu nhiên ban đầu
    long long x = (rand() % (n - 2)) + 2;
    long long y = x;
    long long c = (rand() % (n - 1)) + 1;
    long long d = 1;

    // Vòng lặp Floyd (Rùa và Thỏ)
    while (d == 1) {
        // Rùa đi 1 bước: x = (x^2 + c) % n
        x = (mul_mod(x, x, n) + c) % n;

        // Thỏ đi 2 bước: y = (y^2 + c) % n
        y = (mul_mod(y, y, n) + c) % n;
        y = (mul_mod(y, y, n) + c) % n;

        // Kiểm tra ước chung lớn nhất
        d = gcd(absolute(x - y), n);

        // Nếu d = n, thất bại, cần thử lại với giá trị c khác
        if (d == n) return pollard_rho(n);
    }

    return d;
}

int main() {
    srand(time(NULL));
    long long n;

    printf("Nhap so can phan tich (N): ");
    if (scanf("%lld", &n) != 1) return 1;

    if (n <= 1) {
        printf("Vui long nhap so lon hon 1.\n");
        return 0;
    }

    // Lưu ý: Pollard's rho không phát hiện được số nguyên tố tự nhiên,
    // do đó trong môi trường production, thường phải chạy thuật toán kiểm tra tính nguyên tố (như Miller-Rabin) trước.

    long long factor = pollard_rho(n);
    printf("Mot uoc so khong tam thuong cua %lld la: %lld\n", n, factor);

    return 0;
}

Lưu ý: Pollard's rho không phát hiện được số nguyên tố tự nhiên, do đó trong môi trường production, thường phải chạy thuật toán kiểm tra tính nguyên tố (như Miller-Rabin) trước.

Thuật toán Pollard's Rho

Phân tích thừa số nguyên tố bằng thuật toán Pollard's rho: kết hợp nghịch lý ngày sinh nhật và thuật toán Rùa - Thỏ của Floyd. Xem trực quan dãy số cuộn thành hình chữ ρ và mã nguồn C minh hoạ.

Thuật toán Pollard's Rho

1. Giới thiệu

2. Ý tưởng chính

Cách thức hoạt động

Mô phỏng tương tác

Đã tìm thấy ước số!

3. Mã nguồn C minh hoạ