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

Kiểm tra Solovay-Strassen là kiểm tra nguyên tố xác suất dựa trên ký hiệu Jacobi và công thức Euler: a^((n-1)/2) ≡ (a/n) (mod n) với n nguyên tố.

Thuật toán

1. Nếu n < 2 hoặc n chẵn (>2) → hợp số
2. Lặp k lần:
   1. Chọn a ngẫu nhiên ∈ [2, n-2]
   2. Tính Jacobi symbol J = (a/n)
   3. Tính x = a^((n-1)/2) mod n
   4. Nếu J ≡ 0 (mod n) hoặc x ≠ J (mod n) → hợp số
3. Nếu qua tất cả vòng lặp → có thể là nguyên tố

Cài đặt C++

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>  // swap

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;
}

// Ký hiệu Jacobi (a/n)
int jacobi_symbol(long long a, long long n) {
    if (a == 0) return 0;
    if (a == 1) return 1;
    
    int result = 1;
    
    if (a < 0) {
        a = -a;
        if (n % 4 == 3) result = -result;
    }
    
    while (a != 0) {
        while ((a & 1) == 0) {
            a >>= 1;
            if (n % 8 == 3 || n % 8 == 5) result = -result;
        }
        swap(a, n);
        if (a % 4 == 3 && n % 4 == 3) result = -result;
        a %= n;
        if (a > n / 2) a -= n;
    }
    
    return (n == 1) ? result : 0;
}

// Solovay-Strassen test
bool solovay_strassen(long long n, int iterations) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 0; i < iterations; ++i) {
        long long a = 2 + rand() % (n - 3);  // [2, n-2]
        long long jacob = (n + jacobi_symbol(a, n)) % n;
        long long mod = mod_pow(a, (n - 1) / 2, n);
        
        if (jacob == 0 || mod != jacob) {
            return false;  // Composite
        }
    }
    return true;  // Probably prime
}

int main() {
    srand(time(nullptr));
    int iter = 50;
    
    long long n;
    cout << "Nhap so can kiem tra: ";
    cin >> n;
    
    if (solovay_strassen(n, iter)) {
        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: 24
24 la hop so

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

So sánh các kiểm tra nguyên tố

Lưu ý

• Solovay-Strassen yếu hơn Miller-Rabin (error rate 1/2 vs 1/4 mỗi vòng)
• Cần __int128 cho modular multiplication tránh overflow 64-bit
• Thực tế: Dùng Miller-Rabin deterministic bases cho 64-bit