素数性テスト：ミラーラビン法
1. 序章
前のチュートリアルで、暗号化アルゴリズムの一般的な法則と計算の複雑さを学習しました。
素数性の最も直接的な検証は、試行除算です。 これは、すべての整数で連続的に除算する試みで構成されます。 ただし、必要なのは指数関数であり、多項式時間ではありません。
このチュートリアルでは、因数分解に頼らずに素数であるかどうかを検証するために使用される方法の1つであるミラー-ラビン法について学習します。 より単純な手順である疑似原始性テストのエラー率を減らす方法として、この方法を紹介します。
2. 疑似原始性
合同モジュロは合同関係です。つまり、加算、減算、および乗算の演算と互換性のある同値関係です。 私達は書く：
括弧は、右辺だけでなく、方程式全体に適用されることを意味します（ここ）。
これはbase-ifの擬素数であり、複合であり、次のように発生すると言われています。
この定義により、いくつかの基本的な結論に到達することができます。
- が素数の場合、null以外の擬素数です。
- 疑似原始性の定義を満たさないようなものが見つかった場合、それは確かに複合です。
- 驚くべきことに、その逆は（ほぼ）有効であり、ほぼ完全な素数性チェックを構成します。 手順は、の疑似プライマリ条件を確認することで構成されます。 それが偽の場合、それは絶対的な確実性を持った複合であり、そうでない場合、それは素数である（期待される）。 より正確には、この場合、既知のことは、素数または2進数の擬素数のいずれかです。
次の擬似コードは、最後のポイントで定義された素数性テストを実装します。
PSEUDOPRIME関数は、がプライムであるがベース2の疑似プライムでもある場合にエラーを生成します。 複合の場合、常に正しい結果が得られます。 次のセクションでは、このエラー率を減らす方法を示します。
3. ミラーラビン素数性テスト
Miller-Rabinテストは、PSEUDOPRIME関数に2つの変更を実装します。 1つ目は、単一の基本値を使用するのではなく、ランダムに選択された複数の値を選択することです。 2番目の変更は、重要な数論の定理にあり、次のことを示しています。
2つの数とが与えられます。ここで、は奇数の素数とであり、次の方程式があります。
解決策と。
この定理の結果は、の自明でない平方根が存在する場合、つまり、次のように述べています。
次に、コンポジットです。
この結果に基づいて、ミラーラビンテストは各べき乗剰余を計算し、。の自明でない平方根があるかどうかをチェックします。この場合、テストはCOMPOSITE結果で終了します。
ミラー-ラビン検定は、複合である証明の確率的検索です。
3.1. 証人の概念
それぞれについて、PSEUDOPRIME手順で使用した制御を次のように実現できます。
ただし、証人の概念を導入する方が効率的です。
それが複合的であることを証明するために使用することが可能である場合、複合的である証人であると言われます。
証人の概念は、単純な実装の問題ではありません。 これは理論的な観点からは基本的なものであり、疑似原始性テストよりも強い条件を想定しています。
3.2. ミラーラビン素作用
この手順を構築するための技術的な詳細は省略します。 WITNESS（a、n）関数があるとします。 この関数がTRUEを返す場合、それは絶対的な確実性を備えた複合的な証人です。
擬似コードでは、ミラーラビン手順を示します。ここで、はランダムに選択されたテストする基本値の数です。
リードの1つが複合であるという事実につながるという結論は、常に正しい結果です。
が十分に大きい場合、MILLER-RABIN関数の素数性の結論は正しい可能性が非常に高くなります。 ただし、ベースの選択が不幸な場合、つまり、何も見つからなかった場合でも証人が存在する場合、手順で誤検知が発生する可能性はわずかです。
多くのビットについて、MILLER-RABIN関数は算術演算とビット演算を必要とします。
3.3. ミラーラビンテストエラー
ミラーラビン検定が疑似原始性検定よりも好ましい理由は2つあります。
- 疑似原始性テストでは、エラーの可能性は数によって異なります。 Miller-Rabinテストでは、良い入力も悪い入力もありません。誤差は、基数を選択する際の大きさと幸運によって異なります。
- 目撃者の概念は疑似原始性テストよりも強い条件であるため、エラーの数は少なくなります。
理論は、次の定理によって2番目のポイントを正当化します。
が複合奇数の場合、複合である証人の数は少なくともです。
この結果は、が複合である場合に証人を見つけられない可能性を保証します。
ミラーラビン検定のエラー率の正確な推定値は、次の定理によって提供されます。
奇数の整数と正の整数の場合、ミラーラビン検定でエラーが発生する確率は最大でです。
上記の擬似コードを分析すると、この結果の証明はすぐにわかります。 が複合の場合、2行目と9行目の間のループを実行するたびに、少なくとも証人を発見する可能性があります。 したがって、反復の場合、合計確率はです。
考えられるほとんどすべてのアプリケーションにはAnで十分ですが、用途によっては、はるかに低くなる場合があります。 たとえば、ランダムに選択された大きな整数にミラーラビン検定を適用して大きな素数を見つけたい場合、。だけでは誤検出が発生する可能性が低いことを示すことができます。 ランダムでない数値の場合、エラーの確率が高くなります。
4. 結論
このチュートリアルでは、いくつかの素数性テストの原則について簡単に説明しました。
試行割り算によるテストの非多項性を考えると、代替手順が必要であり、その中で最も単純なのは疑似一次性テストです。 非常に効果的ですが、多くのアプリケーションでは受け入れられない可能性のあるエラー率が発生します。
これは、ミラーラビン検定などのより複雑な方法につながります。
