PHP と GMP を使用して大きな整数のルーカス・レーマー素数性テストを実行する方法

PHP と GMP を使用して大きな整数のルーカス・レーマー素数性テストを実行する方法

はじめに:
整数理論では、ルーカス・レーマー素数性テストはメルネセン数をテストするために使用される方法です。 (メルセンヌ数) 数値が素数かどうかを判定する方法は、大きな整数の判定に広く使用されています。この記事では、PHP 言語と GMP 拡張機能 (GNU Multiple Precision Arithmetic Library、GNU Multiple Precision Math Library) を使用して、Lucas-Lehmer 素数性テストを実装し、対応するコード例を提供します。

ルーカス・レーマーセクシュアリティテストとは何ですか?
Lucas-Lehmer 素数性テストは、M = 2^n − 1 の形式のモネッセン数が素数であるかどうかを判断するために使用される効率的なアルゴリズムです。このうち、nは1以上の正の整数です。この検定方法はルーカス・レーマー数列の性質に基づいており、数列の次の要素を繰り返し計算し、最終的に数列の最後の要素が 0 であるかどうかを判断することでモネッセン数の素数を判定します。

PHP と GMP を使用して Lucas-Lehmer 素数性テストを実行する手順:
ステップ 1: GMP 拡張機能をインストールする
大きな整数演算を実行する場合、PHP の組み込み関数はそれより大きな値を処理できません。したがって、この問題を解決するには GMP 拡張機能を使用する必要があります。 PHP をインストールするときに、GMP 拡張機能が有効になっているバージョンをインストールするか、既存の PHP 環境で GMP 拡張機能を有効にするかを選択できます。

ステップ 2: Lucas-Lehmer 素数性テスト関数を作成する
次は、Lucas-Lehmer 素数性テストを実行するために使用される関数の例です:

function lucasLehmerTest($n)
{
    $s = '4';
    $m = gmp_pow('2', $n) - '1';
    
    for ($i = 1; $i < $n - 1; $i++) {
        $s = gmp_mod(gmp_pow($s, 2) - 2, $m);
    }
    
    if ($s == '0') {
        return true;
    }
    
    return false;
}

分析:

• $n: ムニッセン数の指数部。
• $s: Lucas-Lehmer シーケンスの初期値。
• $m: モネッセン番号。

関数では、gmp_pow 関数を使用して 2 の $n$ 乗を計算し、1 を減算して $m$ を取得します。次に、$n-1$ ループ反復を実行して、Lucas-Lehmer シーケンスの各要素を計算します。最後に、シーケンスの最後の要素がゼロであるかどうかを判断し、それによってモネッセン数の素数性を判断します。

ステップ 3: テストのために Lucas-Lehmer 素数性テスト関数を呼び出す
次は、Lucas-Lehmer 素数性テスト関数を呼び出す例です:

$exponents = [2, 3, 5, 7, 13, 17];
foreach ($exponents as $exponent) {
    $result = lucasLehmerTest($exponent);
    
    if ($result) {
        echo "2^$exponent - 1 is a prime number.
";
    } else {
        echo "2^$exponent - 1 is not a prime number.
";
    }
}

分析:
Weいくつかの指数値を含む配列 $exponents を定義します。次に、foreach ループを使用して Lucas-Lehmer 素数性テスト関数を順番に呼び出し、テスト結果に基づいて対応する判定情報を出力します。

概要:
PHP および GMP 拡張機能を使用すると、Lucas-Lehmer 素数テストを簡単に実装し、大きな整数が素数かどうかを判断できます。大規模な素数性テストの場合、Lucas-Lehmer アルゴリズムは非常に効率的で、メーニセン数の素数性を迅速に決定できます。この記事では、読者が実際に大きな整数の素数性テストを行うのに役立つことを期待して、対応するコード例を提供します。

参考:

• 「Lucas–Lehmer の素数性テスト」。Wikipedia、フリー百科事典。URL: https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test
• 「GMP マニュアル」PHP URL: https://www.php.net/manual/en/book.gmp.php

上記は PHP の使い方と、 GMP 大きな整数の Lucas-Lehmer 素数性テストの実行に関する記事と、対応するコード例。

以上がPHP と GMP を使用して大きな整数のルーカス・レーマー素数性テストを実行する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。