Chương trình C++ kiểm tra số nguyên tố Baillie-PSW

Kiểm tra nguyên tố Baillie-PSW kết hợp kiểm tra Miller-Rabin (cơ sở 2) với kiểm tra Lucas. Đây là một trong những kiểm tra xác suất mạnh nhất — không biết counterexample nào cho số < 2⁶⁴.

Thuật toán

1. Kiểm tra các trường hợp nhỏ (n < 2, n = 2, 3, số chẵn)
2. Viết n-1 = d × 2^s (d lẻ)
3. Miller-Rabin test cơ sở 2
4. Lucas test (tìm D, P, Q thỏa mãn Jacobi(D,n) = -1)

Cài đặt C++ (Đơn giản hóa: chỉ Miller-Rabin)

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Modular exponentiation: (base^exp) % mod
long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Miller-Rabin test cho một base
bool miller_test(long long d, long long n) {
    long long a = 2 + rand() % (n - 4);  // Random base [2, n-2]
    long long x = mod_pow(a, d, n);
    
    if (x == 1 || x == n - 1) return true;
    
    while (d != n - 1) {
        x = (__int128)x * x % n;
        d <<= 1;
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}

// Miller-Rabin lặp k lần
bool isPrime_MillerRabin(long long n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    
    // n-1 = d * 2^s
    long long d = n - 1;
    while ((d & 1) == 0) d >>= 1;
    
    for (int i = 0; i < k; ++i) {
        if (!miller_test(d, n)) return false;
    }
    return true;
}

int main() {
    srand(time(nullptr));
    int iterations = 50;
    
    long long n;
    cout << "Nhap so can kiem tra: ";
    cin >> n;
    
    if (isPrime_MillerRabin(n, iterations)) {
        cout << n << " co the la so nguyen to\n";
    } else {
        cout << n << " la hop so\n";
    }
}

Kết quả mẫu

Nhap so can kiem tra: 23
23 co the la so nguyen to

Nhap so can kiem tra: 45
45 la hop so

Lưu ý về Baillie-PSW đầy đủ

Baillie-PSW thực sự bao gồm:

1. Trial division bởi các số nguyên tố nhỏ
2. Miller-Rabin base 2
3. Lucas probable prime test (tìm tham số D, P, Q)

Cài đặt Lucas test phức tạp hơn, cần:

• Tìm D trong dãy 5, -7, 9, -11, 13... sao cho Jacobi(D, n) = -1
• Tính dãy Lucas U_n, V_n modulo n
• Kiểm tra U_n ≡ 0 (mod n)

Độ tin cậy

• Không có counterexample nào được tìm thấy cho Baillie-PSW (tính đến 2024)
• Được dùng trong nhiều thư viện crypto (GMP, OpenSSL tùy cấu hình)
• Đối với 64-bit: Miller-Rabin với bases {2, 325, 9375, 28178, 450775, 9780504, 1795265022} là định danh (deterministic)

Phiên bản Deterministic 64-bit (Khuyến nghị)

bool isPrime_64bit(uint64_t n) {
    if (n < 2) return false;
    for (uint64_t p : {2,3,5,7,11,13,17,19,23,29,31,37}) {
        if (n % p == 0) return n == p;
    }
    
    uint64_t d = n - 1, s = 0;
    while ((d & 1) == 0) { d >>= 1; s++; }
    
    // 7 bases đủ cho mọi 64-bit
    for (uint64_t a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (a % n == 0) continue;
        uint64_t x = mod_pow(a, d, n);
        if (x == 1 || x == n-1) continue;
        bool composite = true;
        for (uint64_t r = 1; r < s; ++r) {
            x = (__int128)x * x % n;
            if (x == n-1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}