Chương trình C++ triển khai kiểm tra nguyên tố Rabin-Miller

Kiểm tra nguyên tố Rabin-Miller được dùng để xác định xem một số cho trước có phải là số nguyên tố hay không. Nó tương tự như kiểm tra Fermat và kiểm tra Solovay-Strassen. Kiểm tra này đầu tiên được phát hiện bởi nhà toán học Nga M. M. Artjuhov.

Thuật toán

Bắt đầu
    ll mulmod(ll a, ll b, ll m)
    ll x = 0, y = a mod m
    while (b > 0)
        if (b mod 2 == 1)
            x = (x + y) mod m
        y = (y * 2) mod m
        b = b / 2
    trả về x mod m
Kết thúc

Bắt đầu
    ll modulo(ll base, ll e, ll m)
    Khởi tạo:
    ll x = 1
    ll y = base
    while (e > 0)
        if (e mod 2 == 1)
            x = (x * y) mod m
        y = (y * y) mod m
        e = e / 2
    trả về x mod m
Kết thúc

Bắt đầu
    bool Miller(ll p, int iteration)
    if (p < 2)
        trả về false
    if (p != 2 và p mod 2 == 0)
        trả về false
    Tính: ll s = p - 1
    while (s mod 2 == 0)
        s = s / 2
    for i = 0 đến iteration - 1
        ll a = rand() mod (p - 1) + 1, temp = s
        ll mod = modulo(a, temp, p)
        while (temp != p - 1 và mod != 1 và mod != p - 1)
            mod = mulmod(mod, mod, p)
            temp *= 2
        if (mod != p - 1 && temp % 2 == 0)
            trả về false
    trả về true
Kết thúc

Mã ví dụ

#include <iostream>
#include <stdlib.h>
#define ll long long
using namespace std;

ll mulmod(ll a, ll b, ll m) {
    ll x = 0, y = a % m;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x + y) % m;
        }
        y = (y * 2) % m;
        b /= 2;
    }
    return x % m;
}

ll modulo(ll base, ll e, ll m) {
    ll x = 1;
    ll y = base;
    while (e > 0) {
        if (e % 2 == 1)
            x = (x * y) % m;
        y = (y * y) % m;
        e = e / 2;
    }
    return x % m;
}

bool Miller(ll p, int iteration) {
    if (p < 2) {
        return false;
    }
    if (p != 2 && p % 2 == 0) {
        return false;
    }
    ll s = p - 1;
    while (s % 2 == 0) {
        s /= 2;
    }
    for (int i = 0; i < iteration; i++) {
        ll a = rand() % (p - 1) + 1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1) {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int iteration = 10;
    ll num;
    cout << "Nhập số nguyên để kiểm tra nguyên tố: ";
    cin >> num;
    if (Miller(num, iteration))
        cout << num << " là số nguyên tố" << endl;
    else
        cout << num << " không phải là số nguyên tố" << endl;
    return 0;
}

Kết quả đầu ra

Nhập số nguyên để kiểm tra nguyên tố: 26
26 không phải là số nguyên tố