PHP と GMP を使用して大数のフェルマー素数テストを実装する方法

PHP と GMP を使用して大きな数のフェルマー素数性テストを実装する方法

はじめに:
フェルマー素数性テストは、数値が素数かどうかを検出する簡単な方法です。この方法は、p が素数で a が p より小さい正の整数の場合、a^(p-1) ≡ 1 (mod p) であるというフェルマーの小定理に基づいています。この定理により、ランダムに選択された a を使用して、数値が素数であるかどうかをテストできます。この記事では、PHP および GMP ライブラリを使用して、大数のフェルマー素数テストを実装します。

インストールとセットアップ:
まず、PHP および GMP ライブラリがシステムにインストールされていることを確認します。まだインストールしていない場合は、コマンド ラインで次のコマンドを実行してインストールできます。

sudo apt-get install php
sudo apt-get install php-gmp

次に、「fermat_prime.php」というファイルを作成し、テキスト エディタで開きます。

フェルマー素数性テスト関数を実装します:
次のコードを追加してフェルマー素数性テスト関数を実装します:

<?php

function is_prime($n, $k)
{
    if ($n <= 1 || $n == 4) {
        return false;
    }
    if ($n <= 3) {
        return true;
    }
 
    while ($k > 0) {
        // 随机选择一个 [2, $n-2] 之间的整数
        $a = gmp_random_range(2, $n-2);
 
        // 使用 GMP 函数进行幂运算
        $res = gmp_powm($a, $n-1, $n);
 
        // 如果不满足费马小定理，则 n 不是素数
        if (gmp_cmp($res, 1) != 0) {
            return false;
        }
        $k--;
    }
 
    return true;
}

分析コード:

• 関数is_prime2 つのパラメーターを受け入れます。$n はテストする数値、$k はテストの数です。
• 関数は、まず $n が 1 から 4 の間かどうかを確認し、そうであれば false を返します。 。 1も4も素数ではないからです。
• 次に、関数は while ループを使用して $k テストを実行します。各ループで、関数は 2 から $n-2 までの正の整数をランダムに選択し、累乗に GMP 関数 gmp_powm を使用します。
• 最後に、関数は計算されたべき乗が 1 に等しいかどうかを比較します。そうでない場合は、数値が素数ではないことを示す false を返します。
• フェルマーの小定理の検証が $k テストで合格した場合、関数は true を返し、数値が素数である可能性があることを示します。

テスト コード:
コード ファイルの最後に次のコードを追加して、is_prime 関数の効果をテストします:

// 测试1: 检测一个较小的素数
$n = gmp_init("17");
$k = 5;
$result = is_prime($n, $k);
echo $result ? "$n is probable prime
" : "$n is not prime
";
 
// 测试2: 检测一个较大的合数
$n = gmp_init("123456789123456789");
$k = 5;
$result = is_prime($n, $k);
echo $result ? "$n is probable prime
" : "$n is not prime
";

Save andファイルを閉じます。

コードを実行します:
コマンド ラインで次のコマンドを実行してコード ファイルを実行します:

php fermat_prime.php

次に、プログラム出力の結果をコマンドライン:

17 is probable prime
123456789123456789 is not prime

結論:
この記事では、PHP および GMP ライブラリを使用して大数のフェルマー素数検定を実装する方法を紹介します。この簡単なテストで、より大きな数が素数であるかどうかを知ることができます。この方法を使用すると、フェルマーの小定理をより深く理解し、基本的な素数性テスト関数を実装できるようになります。

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