PHP と GMP を使用して大きな整数のフェルマーの定理をテストする方法

PHP と GMP を使用して大きな整数のフェルマーの小定理をテストする方法

フェルマーの小定理は、数論における重要な定理の 1 つです。これは、大きな整数の素数性テストを実行する、つまり、大きな整数が素数であるかどうかを判断するために使用できます。この記事では、PHP と GMP 拡張ライブラリを使用して、大きな整数に対するフェルマーの小定理のテストを実行する方法を紹介します。

まず第一に、フェルマーの定理の原理を理解する必要があります。フェルマーの小定理は次のように表されます。

p が素数、a が任意の整数、a が p で割り切れない場合、a^(p-1) ≡ 1 (mod p) となります。

リトル フェルマーの定理によれば、大きな整数に対してリトル フェルマーの定理をテストできます。具体的な手順は次のとおりです。

ステップ 1: GMP 拡張ライブラリをインポートする

PHP の組み込み関数は大きな整数を処理できないため、大きな整数を処理するには GMP 拡張ライブラリをインポートする必要があります。 。 PHP では、次のコードを通じて GMP 拡張ライブラリをインポートできます。

if (extension_loaded('gmp')) {
    echo "GMP扩展库已加载。
";
} else {
    echo "GMP扩展库未加载。
";
    exit;
}

ステップ 2: 小フェルマー定理テスト関数を実装する

次のように定義することで、大きな整数に対する小フェルマー定理を実装できます。機能テスト。この関数は次のように定義されています:

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可能是素数
}

上記のコードでは、gmp_random_range 関数を使用して 2 から $n-1$ までのランダムな整数 $a$ を生成し、次に gmp_powm 関数を使用して $ を計算します。 a^ {n-1} mod n$ の結果。結果が 1 に等しくない場合、$n$ は素数ではないため false を返します。そうでない場合は、次のテストを続行します。すべてのテストに合格した場合、$n$ はおそらく素数であり、true を返します。

ステップ 3: テスト関数

実装された小フェルマー定理のテスト関数の正確さを検証するテスト関数を作成できます。テスト関数は次のように定義されます。

function testFermatTest($n) {
    if (fermatTest($n, 10)) { // 进行10次小费马定理测试
        echo "{$n} 可能是素数。
";
    } else {
        echo "{$n} 不是素数。
";
    }
}

上記のコードでは、fermatTest 関数を呼び出してフェルマーの定理を 10 回テストし、テスト結果に基づいて対応する情報を出力します。

ステップ 4: テストを実行する

最後に、テスト関数を呼び出して、小さなフェルマー定理テストを実行できます。たとえば、次のコードを使用して、より大きな整数 100000000000000000003 をテストできます。

testFermatTest(gmp_init("100000000000000000003"));

上記のコードでは、gmp_init 関数を使用して文字列 "100000000000000000003" を大きな整数に変換し、フェルマーの定理を実行します。テスト。

上記の手順により、PHP および GMP 拡張ライブラリを使用して、大きな整数の小さなフェルマー定理をテストできます。これは、大きな整数が素数かどうかを判断するためのシンプルかつ効果的な方法です。

実際のアプリケーションでは、フェルマーの定理テストは、テストの精度と信頼性を向上させるために他のテスト方法と組み合わせられることが多いことに注意してください。

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