Miller-Rabin và Pollard's Rho

Wiki › Thuật toán › Toán học

huunguyen · Last updated 8, Tháng 4, 2026, 16:11

Miller-Rabin kiểm tra số nguyên tố trong $O (K \log^{2} N)$ và Pollard's Rho phân tích thừa số nguyên tố trong $O (N^{1 / 4} polylog)$ — hiệu quả cho $N \leq 10^{18}$ .

Miller-Rabin

Kiểm tra $N$ có nguyên tố không bằng cách kiểm tra điều kiện Fermat mạnh với một số cơ sở $a$ .

Nguyên lý: Nếu $N$ nguyên tố và $N - 1 = 2^{r} \cdot d$ , thì với mọi $a$ nguyên tố cùng nhau với $N$ :

$a^{d} \equiv 1 (\mod N)$ , hoặc
$a^{2^{j} d} \equiv - 1 (\mod N)$ với một $j \in [0, r)$ .

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % 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;
}

bool miller_rabin(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1; int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ll x = power(a, d, n);
    if (x == 1 || x == n-1) return true;
    for (int i = 0; i < r-1; i++) {
        x = mulmod(x, x, n);
        if (x == n-1) return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    // Các cơ sở này đủ cho n < 3.3 * 10^24 (deterministic)
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
        if (!miller_rabin(n, a)) return false;
    return true;
}

Độ phức tạp: $O (12 \log^{2} N)$ — nhanh hơn $O (\sqrt{N})$ rất nhiều với $N \leq 10^{18}$ .

Pollard's Rho

Tìm một ước nguyên tố của $N$ trong $O (N^{1 / 4} polylog)$ bằng phương pháp cycle detection của Floyd.

ll pollard_rho(ll n) {
    if (n % 2 == 0) return 2;
    ll x = rand() % (n-2) + 2;
    ll y = x;
    ll c = rand() % (n-1) + 1;
    ll d = 1;
    while (d == 1) {
        x = (mulmod(x, x, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        d = __gcd(abs(x - y), n);
    }
    return d;
}

// Phiên bản Brent (nhanh hơn)
ll brent(ll n) {
    if (n % 2 == 0) return 2;
    ll y = rand() % (n-1) + 1, c = rand() % (n-1) + 1, m = rand() % (n-1) + 1;
    ll g = 1, q = 1, r = 1, ys, x;
    while (g == 1) {
        x = y;
        for (ll i = 0; i < r; i++) y = (mulmod(y, y, n) + c) % n;
        ll k = 0;
        while (k < r && g == 1) {
            ys = y;
            for (ll i = 0; i < min(m, r-k); i++) {
                y = (mulmod(y, y, n) + c) % n;
                q = mulmod(q, abs(x-y), n);
            }
            g = __gcd(q, n);
            k += m;
        }
        r <<= 1;
    }
    if (g == n) {
        while (true) {
            ys = (mulmod(ys, ys, n) + c) % n;
            g = __gcd(abs(x - ys), n);
            if (g > 1) break;
        }
    }
    return g;
}

Phân tích thừa số nguyên tố hoàn chỉnh

map<ll, int> factorize(ll n) {
    map<ll, int> factors;
    function<void(ll)> factor = [&](ll n) {
        if (n == 1) return;
        if (is_prime(n)) { factors[n]++; return; }
        ll d = n;
        while (d == n) d = brent(n);
        factor(d); factor(n / d);
    };
    factor(n);
    return factors;
}

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

So sánh với sàng nguyên tố

	Sàng Eratosthenes	Miller-Rabin	Pollard's Rho
Kiểm tra nguyên tố $N$	$O (\sqrt{N})$ sau sàng	$O (\log^{2} N)$	—
Phân tích $N$	$O (\sqrt{N})$	—	$O (N^{1 / 4})$
Giới hạn $N$	$\leq 10^{7}$ (sàng)	$\leq 10^{18}$	$\leq 10^{18}$

Khi nào dùng Miller-Rabin / Pollard's Rho?

$N \leq 10^{18}$ : quá lớn cho sàng hoặc $O (\sqrt{N})$ .
Kiểm tra nhiều số nguyên tố lớn nhanh.
Phân tích thừa số nguyên tố của số lớn (tính $ϕ (N)$ , số ước,...).

Bình luận

Không có bình luận tại thời điểm này.