使用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扩展库，我们能够实现对大整数的有效小费马定理测试。该方法简单实用，适合对大数素性进行初步判断。不过，为提升准确度，通常会将小费马测试与其他素性检测算法联合使用。