Miller-Rabin Primality Test

Ý tưởng chủ đạo

Thuật toán Miller-Rabin dựa trên nguyên lý của định lý Fermat nhỏ:

Nếu $p$ là số nguyên tố, thì ta có \(a^p \equiv a (\bmod p)\).

Tuy nhiên, vấn đề là đối với một số nguyên $n$ bất kỳ thỏa mãn \(a^n \equiv a (\bmod n)\) với $a$ là số tự nhiên, thì chưa chắc $n$ đã là số nguyên tố. Nói cách khác, nếu $n$ vượt qua phép thử Fermat trên, vẫn tồn tại một khả năng nhỏ $n$ là hợp số. Thuật toán Miller-Rabin mở rộng phép thử Fermat từ nhận xét:

• \(a^n \equiv a (\bmod n) \iff a^{n-1} \equiv 1 (\bmod n)\)

• Với mọi $n$, luôn có thể phân tích \(n-1 = 2^s \times d\), với $d$ là số lẻ

• Từ đó ta phân tích \(a^{n-1} \equiv 1 (\bmod n)\) thành: \(a^{n-1} - 1 = a^{2^s \times d} - 1 = (a^{2^{s-1} \times d} + 1)(a^{2^{s-2} \times d} + 1)\dots(a^d + 1)(a^d-1) \equiv 0 (\bmod n)\)Nếu $n$ là số nguyên tố thì phải tồn tại ít nhất một thừa số chia hết cho $n$.

Như vậy ta sẽ kiểm trả các điều kiện:

• Hoặc \(n|(a^d-1) \implies a^d \equiv 1 (\bmod n)\)

• Hoặc có ít nhất một thừa số \((a^{2^i\times d} + 1), 0\le i \le s-1\) chia hết cho $n$, hay \(a^{2^i\times d} \equiv -1 (\bmod n)\)

Nếu $n$ không thỏa cả 2 điều kiện trên thì $n$ chắc chắn là hợp số, ngược lại thì $n$ có khoảng 25% khả năng là một số nguyên tố. Như vậy, để chắc chắn hơn, ta có thể kiểm tra nhiều lần với nhiều giá trị $a$ khác nhau để tăng xác suất.

Thuật toán

Kiểm tra $n$ có phải số nguyên tố hay không, lưu ý rằng thuật toán dưới đây nếu trả về TRUE thì $n $ có thể là số nguyên tố, ngược lại nếu FALSE thì $n$ chắc chắc là hợp số.

• Phân tích \(n = 2^s\times d +1\)

• Chọn số ngẫu nhiên \(a \in [2, n-1]\):

  • Nếu \(a^d \bmod n = 1\): return TRUE

• Cho \(i: 1 \to k-1:\)

  • Nếu \(a^{2^i\times d} \bmod n = 1\): return TRUE

• Return FALSE

Cài đặt và Demo

Phân tích một số thành dạng \(2^s \times d\)

// factorize n to the format of 2^s * d
    function factorize(n) {
        let s = 0;
        let d = n;
        while (d % 2 == 0) {
            s++;
            d = d >> 1;
        }
        return [s, d];
    }

Thuật toán

function rabinMiller(n, s, d, a) {
            // first condition check a^d mod n = 1
            if (modPow(a, d, n) == 1) return true;

            // second condition check a^(2^i * d) mod n = n - 1
            for (let i = 0; i < s; i++) {
                if (modPow(a, (2**i) * d, n) == n - 1) return true;                
            }           

            // if both conditions fail, n is composite
            return false;
        }

Mình đã thử chạy thử thuật toán với 10 lần thử (10 lần chọn $a$ ngẫu nhiên) này để đếm xem có bao nhiêu số nguyên tố trong khoảng từ 1-10,000,000 và kết quả là có 664,579 số nguyên tố.

let total = 0;
let trials = 10;
for (let i = 0; i < 10000000; i++) {
    if (isPrime(i, trials)) {
        console.log(i);
        total++;
    }
}
console.log(`Total prime numbers: ${total}`);

Demo