使用PHP與GMP擴展實現大整數小費馬定理素性測試方法

小費馬定理簡介

小費馬定理是數論中的基礎定理之一，廣泛應用於素數檢測。定理指出：如果p是素數，且a為不被p整除的任意整數，則有a^{p-1} \equiv 1 \pmod{p} 。這一定理可用於驗證一個大整數是否為素數。

引入GMP擴展處理大整數

由於PHP原生函數在處理超大整數時存在限制，GMP擴展提供了高效的多精度整數運算支持。首先需要確認GMP擴展已加載，示例如下：

 if (extension_loaded('gmp')) {
    echo "GMP擴展庫已加載。";
} else {
    echo "GMP擴展庫未加載。";
    exit;
}

實現小費馬定理測試函數

通過定義一個函數，使用GMP的多精度運算函數進行多輪隨機測試，判斷大整數的素性：

 function fermatTest($n, $k) {
    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n - 1);  // 隨機選擇整數a
        $result = gmp_powm($a, $n - 1, $n);  // 計算 a^(n-1) mod n
        if (gmp_cmp($result, 1) !== 0) {  // 結果不為1，n非優勢數字
            return false;
        }
    }
    return true;  // 通過所有測試，n可能為素數
}

測試函數的實現

為了驗證小費馬測試函數的準確性，可以定義一個輔助測試函數，調用上述方法多次驗證：

 function testFermatTest($n) {
    if (fermatTest($n, 10)) {  // 進行10次小費馬測試
        echo "{$n} 可能是素數。";
    } else {
        echo "{$n} 不是素數。";
    }
}

執行測試示例

下面示例展示瞭如何對一個超大整數進行小費馬定理素性測試：

 <span class="fun">testFermatTest(gmp_init("100000000000000000003"));</span>

代碼中通過gmp_init將字符串轉換為GMP大整數，再調用測試函數執行檢測。

總結

通過以上步驟，結合PHP的GMP擴展庫，我們能夠實現對大整數的有效小費馬定理測試。該方法簡單實用，適合對大數素性進行初步判斷。不過，為提升準確度，通常會將小費馬測試與其他素性檢測算法聯合使用。