PHP と GMP を使用して大数の Miller-Rabin 素数テストを実装する方法

PHP と GMP を使用して大数の Miller-Rabin 素数性テストを実装する方法

はじめに:
素数は暗号化とコンピューター サイエンスで重要な役割を果たします。 Miller-Rabin 素数性テストは、数値が素数であるかどうかをテストするために使用される確率的アルゴリズムであり、高い確率で正しい答えが得られます。この記事では、PHP 言語と GMP ライブラリ (GNU Multiple Precision Arithmetic Library) を使用して、大数に対する Miller-Rabin 素数性テスト アルゴリズムを実装する方法を紹介します。

GMP ライブラリの紹介:
GMP ライブラリは、高精度計算のためのオープン ソース ライブラリであり、大きな整数をサポートします。 GMP ライブラリを使用すると、大きな数の加算、減算、乗算、除算などの演算を含む大きな数の計算を処理できます。

アルゴリズム原理:
Miller-Rabin の素数性テスト アルゴリズムは、フェルマーの小定理の拡張に基づいています。この定理は次のように述べています。素数 p と整数 a が互いに素であり、a^(p-1) ≡ 1 (mod p) である場合、a は p の基数であり、p は塩基の半分以上を持ちます。

ミラー・ラビンの素数性検定アルゴリズムによれば、異なる基数を複数回選択することで、ある数値が素数であるかどうかを一定の確率で判定できます。アルゴリズムの考え方は、テストされる数値 n ごとにランダムな基数 b を選択し、a^d ≡ 1 (mod n) および a^(2^r*d) ≡ -1 (mod n) を計算するというものです。 ) それが真かどうかはわかりませんが、真であれば n は素数である可能性があり、そうでない場合は n が合成数であると確信できます。

コード例:

<?php

// 导入GMP库
if (!extension_loaded('gmp')) {
    dl('gmp.so');
}

function millerRabinTest($n, $k = 20) {
    if ($n <= 1 || $n == 4) {
        return false;
    }
    if ($n <= 3) {
        return true;
    }

    // 将$n-1表示为(2^r) * d的形式
    $r = 0;
    $d = $n - 1;
    while (gmp_mod($d, 2) == 0) {
        $d >>= 1;
        $r++;
    }

    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n - 2);
        $x = gmp_powm($a, $d, $n);

        if ($x == 1 || $x == $n - 1) {
            continue;
        }

        $continueLoop = false;
        for ($j = 0; $j < $r - 1; $j++) {
            $x = gmp_powm($x, 2, $n);
            if ($x == 1) {
                return false;
            }
            if ($x == $n - 1) {
                $continueLoop = true;
                break;
            }
        }

        if (!$continueLoop) {
            return false;
        }
    }

    return true;
}

// 测试示例
$numbers = [
    gmp_init('2'),
    gmp_init('3'),
    gmp_init('4'),
    gmp_init('17'),
    gmp_init('7919'),
    gmp_init('999999999999999993')
];

foreach ($numbers as $number) {
    echo gmp_strval($number) . ' is ' . (millerRabinTest($number) ? 'prime' : 'composite') . PHP_EOL;
}

この例では、millerRabinTest() 関数を使用して、数値が素数かどうかをテストします。パラメーター $k は、テストの反復数を表します。このテスト例では、いくつかの数値を個別にテストし、テスト結果を出力しました。

概要:
Miller-Rabin 素数性テスト アルゴリズムは、特に大きな数に適した効率的な素数性検出アルゴリズムです。 PHP 言語と GMP ライブラリを使用すると、このアルゴリズムを簡単に実装できます。 Miller-Rabin の素数性テストを通じて、数値が素数であるかどうかを効果的に判断できるため、暗号化、セキュリティ、その他の分野で強力なツールが提供されます。

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