Miller-Rabin演算法詳解

一、演算法簡介

Miller-Rabin演算法是一種基於費馬小定理的素性測試（Primality Test）演算法，主要用於判斷一個數是否為素數。演算法時間複雜度為O(k*log^3(n))，其中k為測試次數，n為待測試的數。

與其它素性測試演算法相比，Miller-Rabin演算法不需要計算大數的因子，因此在實際應用中更加高效。同時，Miller-Rabin演算法也被廣泛應用於RSA演算法和密碼學領域中的其它問題。

二、演算法思路

Miller-Rabin演算法的核心思想是利用費馬小定理：如果p是素數，a是p的任意正整數且a<p，則a^(p-1) mod p ≡ 1。

我們可以使用上述式子來判斷一個數是否為素數：首先隨機選擇一個小於該數的正整數a，將a^(n-1) mod n計算出來，若該值不等於1，則說明n為合數；反之，則繼續進行下一輪測試。若經過多輪測試，n仍然沒有被認定為合數，則說明n很可能是素數。

三、演算法實現

在實現Miller-Rabin演算法時，主要包括兩個步驟：隨機選擇值a和測試n是否為素數。

// 隨機選擇a
int rand_a(int n) {
    return rand() % (n - 2) + 2;
}

// 計算x的k次冪，並取模運算
int pow_mod(int x, int k, int p) {
    int ans = 1;
    while (k) {
        if (k & 1)
            ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}

// Miller-Rabin演算法
bool is_prime(int n, int test_cnt) {
    if (n >= 1;
        k++;
    }

    for (int i = 0; i < test_cnt; i++) {
        int a = rand_a(n);
        int x = pow_mod(a, m, n);
        if (x == 1)
            continue;
        for (int j = 0; j < k; j++) {
            if (x == n - 1)
                break;
            x = pow_mod(x, 2, n);
        }
        if (x != n - 1)
            return false;
    }
    return true;
}

四、演算法分析

Miller-Rabin演算法的正確性是基於費馬小定理，即如果n為素數，則對於任意的a(1<a<n)，都有a^(n-1) mod n=1，而對於合數可能僅在a^(n-1) mod n≠1時被檢測出來（發生概率極小），因此在測試次數足夠多的情況下，Miller-Rabin演算法的錯誤率可以被控制在極小範圍內。

在實際應用中，Miller-Rabin演算法的測試次數通常為15~20次，可以滿足絕大部分情況下的精度要求。同時，與其它素性測試演算法相比，Miller-Rabin演算法更為高效，因此被廣泛應用於密碼學領域。但需要指出的是，Miller-Rabin演算法並不是完全精確的，仍然有可能出現誤判的情況，因此在實際應用中需要進行綜合評估和分析。