PHPとGMPを使用して大量のLucas-Lehmer品質テストを実装する方法

M66 2025-06-19

PHPとGMPを使用して多数のLucas-Lehmerプライメネステストを実装する方法

Lucas-Lehmerプライマリテストは、Mersenneの数を判断するために一般的に使用されるアルゴリズムであり、数の理論と暗号化で広く使用されています。 Mersenne数は、フォーム2 ⁿ -1の整数であり、nは正の整数です。この記事では、PHPおよびGMPライブラリを使用してこのプライムテストを実装して、Mersenne番号がプライム番号であるかどうかを判断する方法を示します。

GMPライブラリをインストールして構成します

まず、PHP環境にGMPライブラリがインストールされていることを確認してください。 phpinfo（）コマンドを使用して、GMPライブラリがインストールされているかどうかを確認できます。インストールされていない場合は、PHPをコンパイルするときにGMPオプションを有効にするか、Linux Systemのパッケージマネージャーからインストールできます。

Lucas-Lehmerプライマリテスト機能の実装

PHPでは、GMPライブラリを使用して大量の操作を実行できます。 Lucas-Lehmerプリミティブテストを実装するPHP関数の例を次に示します。

 
function lucasLehmerTest($n) {
    $s = gmp_init(4);
    $m = gmp_sub(gmp_pow(2, $n), 1);

    for ($i = 0; $i < $n - 2; $i++) {
        $s = gmp_mod(gmp_sub(gmp_mul($s, $s), 2), $m);
    }

    return gmp_cmp($s, 0) == 0;
}

この関数は、Mersenne番号の指数を表すパラメーターnを受け入れます。この関数は、Lucas-Lehmerシーケンスの各アイテムを計算し、最後のアイテムが0であるかどうかをチェックします。Trueが返された場合、Mersenne番号が素数であることを意味します。 Falseが返された場合、Mersenne番号が素数ではないことを意味します。

Lucas-Lehmerプライマリテスト関数を呼び出します

次に、上記の関数を使用して、Mersenne番号のプロパティテストを実行できます。 Mersenne番号が素数であるかどうかを検出する例は次のとおりです。

 
$n = 29; // 適切なインデックスを選択します，ここ29例として
$isPrime = lucasLehmerTest($n);

if ($isPrime) {
    echo "2^{$n} - 1 それは主要な数字です";
} else {
    echo "2^{$n} - 1 不それは主要な数字です";
}

この例では、テスト用に29のインデックスを選択し、Mersenne番号が返品値に基づいてプライム番号であるかどうかを判断しました。

パフォーマンスの最適化

Lucas-Lehmerプライマリテストは大量に計算されるため、より大きなN値には長い時間がかかる場合があります。パフォーマンスを改善するために、次の最適化戦略を考慮することができます。

N自体が素数である場合、2 ⁿ -1もプライム番号である可能性があります。
nは、偶数nの無効な計算を避けるために奇数でなければなりません。
64未満のn値を除外します。これらのケースは検証されています。

これらの最適化により、特により大きなMersenne数を扱う場合、アルゴリズムの走行速度を大幅に改善できます。

結論は

この記事では、PHPおよびGMPライブラリを使用してLucas-Lehmer Primenessテストを実装する方法を紹介します。大規模な操作にGMPを使用することにより、Mersenne番号が素数であるかどうかを効果的に判断できます。さらに、計算をスピードアップするのに役立つパフォーマンス最適化の提案が提供されています。この記事が、このアルゴリズムを理解することに興味がある読者に役立つことを願っています。