Wiki › Thuật toán › Toán học › Miller-Rabin và Pollard's Rho

Miller-Rabin và Pollard's Rho

huunguyen Updated Tháng sáu 1, 2026

Khi cần kiểm tra một số $N$ rất lớn (tới $10^{18}$ ) có phải số nguyên tố hay không, hoặc phân tích nó thành tích các thừa số nguyên tố, cách ngây thơ thử mọi ước tới $\sqrt{N}$ tốn $O (\sqrt{N}) \approx 10^{9}$ phép tính — quá chậm. Miller-Rabin kiểm tra nguyên tố trong $O (K \log^{2} N)$ (chỉ vài chục phép nhân lớn), còn Pollard's Rho tìm một ước không tầm thường của $N$ trong khoảng $O (N^{1 / 4})$ kỳ vọng. Kết hợp hai thuật toán này, ta phân tích thừa số một số $\leq 10^{18}$ gần như tức thì.

Ý tưởng / Trực giác

Miller-Rabin — tại sao đúng?

Xuất phát từ định lý Fermat nhỏ: nếu $N$ nguyên tố thì $a^{N - 1} \equiv 1 (\mod N)$ với mọi $a$ không chia hết cho $N$ . Nhưng điều ngược lại không đúng (có số giả nguyên tố Fermat, vd số Carmichael như $561$ qua được test Fermat với mọi cơ sở). Miller-Rabin mạnh hơn nhờ khai thác thêm một tính chất:

Trong trường $ℤ_{N}$ khi $N$ nguyên tố, phương trình $x^{2} \equiv 1$ chỉ có đúng hai nghiệm là $x \equiv 1$ và $x \equiv - 1$ . Viết $N - 1 = 2^{r} \cdot d$ với $d$ lẻ. Dãy

$a^{d}, a^{2 d}, a^{4 d}, \dots, a^{2^{r - 1} d}, a^{2^{r} d} = a^{N - 1}$

là dãy "bình phương liên tiếp", kết thúc ở $1$ (theo Fermat). Lần đầu tiên dãy chạm $1$ , phần tử ngay trước nó là một căn bậc hai của $1$ . Nếu $N$ nguyên tố, căn đó bắt buộc là $1$ hoặc $- 1$ . Vậy điều kiện cần để $N$ nguyên tố là:

$a^{d} \equiv 1 (\mod N)$ , hoặc
tồn tại $j \in [0, r)$ sao cho $a^{2^{j} d} \equiv - 1 (\mod N)$ .

Nếu với cơ sở $a$ nào đó cả hai điều này đều sai thì ta tìm được một căn bậc hai "lạ" của $1$ — bằng chứng chắc chắn $N$ là hợp số. Khi đó $a$ gọi là nhân chứng (witness). Định lý cho biết với mỗi hợp số lẻ, ít nhất $3 / 4$ số cơ sở là nhân chứng, nên thử nhiều cơ sở thì xác suất sai giảm rất nhanh. Với $N < 3.3 \times 10^{24}$ , dùng cố định 12 cơ sở ${2, 3, 5, \dots, 37}$ là xác định (deterministic) — không còn xác suất.

Pollard's Rho — tại sao tìm được ước?

Giả sử $N$ có ước nguyên tố $p \leq \sqrt{N}$ . Sinh một dãy "giả ngẫu nhiên" bằng hàm $f (x) = (x^{2} + c) mod N$ :

$x_{0}, x_{1} = f (x_{0}), x_{2} = f (x_{1}), \dots$

Xét dãy này theo modulo $p$ . Vì chỉ có $p$ lớp dư, theo nguyên lý chuồng bồ câu dãy $x_{i} mod p$ sẽ lặp lại sau khoảng $O (\sqrt{p})$ bước (nghịch lý ngày sinh), tạo thành hình chữ "ρ" (rho). Khi $x_{i} \equiv x_{j} (\mod p)$ nhưng $x_{i} \neq x_{j}$ (theo modulo $N$ ), thì $| x_{i} - x_{j} |$ là bội của $p$ nhưng không phải bội của $N$ , nên

$gcd (| x_{i} - x_{j} |, N)$

là một ước thực sự của $N$ . Ta dùng phát hiện chu trình kiểu Floyd/Brent để bắt cặp $(i, j)$ đó. Vì $p \leq \sqrt{N}$ nên chỉ cần $O (\sqrt{p}) = O (N^{1 / 4})$ bước kỳ vọng.

Pollard's Rho chỉ cho một ước bất kỳ (chưa chắc nguyên tố). Ghép với Miller-Rabin để biết khi nào dừng: nếu phần còn lại đã nguyên tố thì ghi nhận, ngược lại tiếp tục tách.

Ví dụ chạy tay

Miller-Rabin với $N = 561$ (số Carmichael), cơ sở $a = 2$

$N - 1 = 560 = 2^{4} \cdot 35$ , vậy $d = 35$ , $r = 4$ .

Tính $x = 2^{35} mod 561 = 263$ . Vì $x \neq 1$ và $x \neq 560$ , ta bình phương liên tiếp và so với $N - 1 = 560$ :

bước j   giá trị x = 2^(2^j · 35) mod 561   so với 1?  so với 560?
  0       263                                 không      không
  1       263^2 mod 561 = 166                  không      không
  2       166^2 mod 561 = 67                   không      không
  3        67^2 mod 561 = 1   <-- căn bậc 2 của 1 mà KHÁC ±1!

Tại bước $j = 3$ ta được $x = 1$ trong khi phần tử trước ( $67$ ) không phải $\pm 1$ . Đây là căn bậc hai "lạ" của $1$ $\Rightarrow$ 561 là hợp số (đúng: $561 = 3 \cdot 11 \cdot 17$ ). Test Fermat thường bị $561$ qua mặt, nhưng Miller-Rabin bắt được ngay.

Pollard's Rho với $N = 8051$ , $c = 1$ , $x_{0} = 2$

$f (x) = (x^{2} + 1) mod 8051$ . Dùng Floyd: $x$ chạy 1 bước, $y$ chạy 2 bước, xét $gcd (| x - y |, N)$ .

vòng   x      y       |x - y|   gcd(|x-y|, 8051)
  1     5      26        21          1
  2    26     7474      7448         1
  3   677     871       194         97   <-- > 1, tìm thấy ước!

$gcd = 97$ là ước của $8051$ . Thật vậy $8051 = 97 \times 83$ . Chỉ sau 3 vòng thay vì thử chia tới $\sqrt{8051} \approx 89$ lần.

Cài đặt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

// Nhân modulo an toàn cho tới 2^63 nhờ __int128 (tránh tràn long long)
ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

// Lũy thừa nhanh: a^b mod m
ll power(ll a, ll b, ll m) {
    ll res = 1; a %= m;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
    }
    return res;
}

// Một lần kiểm tra Miller-Rabin với cơ sở a. true = "có thể nguyên tố"
bool check_composite(ll n, ll a, ll d, int r) {
    ll x = power(a, d, n);
    if (x == 1 || x == n - 1) return false; // qua được, chưa kết luận hợp số
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return false;       // gặp -1, qua được
    }
    return true;                            // không bao giờ gặp 1 hay -1 => hợp số
}

bool is_prime(ll n) {
    if (n < 2) return false;
    // Tách n - 1 = 2^r * d, d lẻ
    int r = 0; ll d = n - 1;
    while ((d & 1) == 0) { d >>= 1; r++; }
    // 12 cơ sở này XÁC ĐỊNH với mọi n < 3.3 * 10^24
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a) return true;            // n nhỏ trùng cơ sở thì nguyên tố
        if (check_composite(n, a, d, r)) return false;
    }
    return true;
}

// Pollard's Rho (bản Brent): trả về một ước KHÔNG TẦM THƯỜNG của n
ll pollard(ll n) {
    if (n % 2 == 0) return 2;
    ll x = rand() % (n - 2) + 2, y = x, c = rand() % (n - 1) + 1, d = 1;
    auto f = [&](ll v) { return (mulmod(v, v, n) + c) % n; };
    while (d == 1) {
        x = f(x);
        y = f(f(y));                        // y chạy nhanh gấp đôi (Floyd)
        d = __gcd(abs(x - y), n);
    }
    return d == n ? pollard(n) : d;         // xui (d==n) thì đổi c, thử lại
}

// Phân tích đệ quy, gom vào map<thừa số, số mũ>
void factorize(ll n, map<ll,int>& factors) {
    if (n == 1) return;
    if (is_prime(n)) { factors[n]++; return; }
    ll d = pollard(n);
    factorize(d, factors);
    factorize(n / d, factors);
}

int main() {
    srand(time(0));
    ll n; cin >> n;
    map<ll,int> f;
    factorize(n, f);
    for (auto [p, e] : f) cout << p << "^" << e << " ";
}

Độ phức tạp

Miller-Rabin: mỗi cơ sở cần một lũy thừa modulo $O (\log N)$ phép nhân, mỗi phép nhân __int128 là $O (1)$ (hoặc $O (\log N)$ nếu tính theo độ dài bit), thêm $r \leq \log N$ lần bình phương. Với $K$ cơ sở cố định ( $K = 12$ ), tổng cộng $O (K \log^{2} N)$ — chỉ vài nghìn phép tính cho $N \approx 10^{18}$ , so với $O (\sqrt{N}) \approx 10^{9}$ của cách chia thử.

Pollard's Rho: với ước nguyên tố nhỏ nhất $p$ , kỳ vọng $O (\sqrt{p})$ bước, mà $p \leq \sqrt{N}$ nên $O (N^{1 / 4})$ bước; mỗi bước có một gcd $O (\log N)$ , vậy $O (N^{1 / 4} \log N)$ mỗi lần tách. Phân tích đầy đủ gọi đệ quy $O (\log N)$ tầng (mỗi tầng cắt đôi giá trị), tổng $\approx O (N^{1 / 4} \log^{2} N)$ .

Bộ nhớ: $O (\log N)$ cho ngăn xếp đệ quy và $O (# thừa số phân biệt)$ cho map — không đáng kể, $O (1)$ thực tế.

⚠️ Lỗi thường gặp

Tràn số khi nhân modulo. Với $N$ tới $10^{18}$ , phép a * b của hai số $< N$ vượt xa giới hạn long long ( $\approx 9.2 \times 10^{18}$ ). Phải ép kiểu (__int128)a * b % m. Quên ép kiểu là nguyên nhân sai phổ biến nhất, và lỗi chỉ lộ ra với test lớn.
Quên trường hợp $n$ nhỏ trùng cơ sở. Nếu $n = 2, 3, \dots, 37$ thì trong vòng lặp Miller-Rabin có thể tính power(a, d, n) với a == n (tức $a \equiv 0$ ), cho kết quả $0$ và kết luận sai "hợp số". Phải kiểm if (n == a) return true; (hoặc xử lý $n < 2$ và các số nhỏ trước).
Pollard's Rho bị kẹt khi $n$ là số nguyên tố. Nếu lỡ gọi pollard trên một số nguyên tố, vòng while (d == 1) có thể chạy rất lâu rồi mới trả $d = n$ . Luôn gọi is_prime trước để chặn, và chỉ pollard trên hợp số.
Lấy $d = n$ (gcd ra chính nó). Khi $x \equiv y (\mod N)$ trước khi tách được, gcd trả về $n$ — không phải ước thực sự. Phải đổi hằng số $c$ (hoặc điểm xuất phát) và thử lại, như dòng return d == n ? pollard(n) : d;. Bỏ qua bước này sẽ cho ước sai $= n$ .
abs với long long. Dùng abs(x - y) mà include sai header có thể gọi abs(int) làm cụt giá trị. Dùng llabs, std::abs (với <cmath>/<cstdlib> đúng) hoặc tự viết x > y ? x - y : y - x.
Dùng quá ít cơ sở rồi tưởng là xác định. Chỉ cơ sở ${2, 3}$ không đủ — có hợp số qua mặt (vd $1373653$ ). Để xác định tới $10^{18}$ , dùng đủ bộ 12 cơ sở (hoặc bộ 7 cơ sở đã chứng minh cho $< 3.2 \times 10^{18}$ : ${2, 3, 5, 7, 11, 13, 17}$ ).

Biến thể / Mở rộng

Miller-Rabin xác suất: khi $N$ vượt $10^{24}$ (vd dùng số nguyên lớn), chọn ngẫu nhiên $k$ cơ sở; xác suất báo sai $\leq 4^{- k}$ .
Brent's improvement: gộp nhiều hiệu $| x - y |$ vào một tích rồi mới gcd một lần (giảm số lần gcd ~ $\log N$ lần) — phiên bản trong nội dung cũ của trang chính là biến thể này.
Ứng dụng phân tích thừa số: từ $N = \prod p_{i}^{e_{i}}$ tính được hàm Euler $φ (N) = N \prod (1 - 1 / p_{i})$ , số ước $\prod (e_{i} + 1)$ , tổng ước, căn nguyên thủy... Xem thêm Toán học.

Bài tập luyện

Kiểm Tra Số Nguyên Tố (primechk) — (Beginner) Kiểm tra một số $N \leq 10^{6}$ có nguyên tố không — khởi động với chia thử, rồi thử cài Miller-Rabin để làm quen điều kiện Fermat mạnh.
Số nguyên tố tiếp theo (nextprime) — (Intermediate) Tìm số nguyên tố nhỏ nhất lớn hơn $n \leq 10^{12}$ ; chia thử $O (\sqrt{n})$ đã chậm, Miller-Rabin là lời giải tự nhiên.
Phân tích ước số (divanal) — (Intermediate) Tính số ước, tổng ước, tích ước từ phân tích thừa số nguyên tố — luyện các công thức ước số sau khi đã có phân tích.
Bội số nguyên tố (primemult) — (Advanced) Đếm số trong $[1, n]$ với $n \leq 10^{18}$ chia hết cho ít nhất một trong $k$ số nguyên tố — bao hàm–loại trừ trên tập thừa số, cần xử lý số rất lớn.