与えられた数の素数性をテストするためのミラーラビンアルゴリズムとは何ですか？

Miller Rabinは、多数の素数性をテストするための高速なアプローチです。このアルゴリズムはラビンミラー素数性テストと呼ばれ、このアルゴリズムは、フェルマーの素数性テストやソロベイ-シュトラッセンの素数性テストなどの他のテストと同じ数が素数であるかどうかを判断します。

このテストは、素数値に当てはまる同等性または同等性のグループに基づいているため、素数性をテストする必要があるかどうかをチェックします。

このアルゴリズムは、最も有用な既知の素数テストアルゴリズムであり、RSA暗号化に基づくさまざまなソフトウェアライブラリで使用でき、最適なインスタンスはOpenSSLです。

ミラーラビンは、数値が合成数であることを検証します。したがって、これは素数性テストではなく複合性テストと呼ばれます。ミラーラビン素検定は、すべての複合材料を識別します。合成数nごとに、少なくとも3/4（ミラーラビン）の数が存在する可能性があります。aはnの合成数の目撃者です。

ミラーラビンは、フェルマーの小定理の連想的に単純な拡張であり、フェルマーの小定理よりもはるかに高い確率で素数性をテストすることができます。

アルゴリズム ：ミラーラビン検定の擬似コード-

Miller-Rabin-Test (n, a) // n is the number; a is the base
{
   Find m and k such that n − 1 = m x 2k
   T ← am mod n
   If (T = ±1)return "a prime"
   for (i ← 1 to k − 1) // k – 1 is the maximum number of steps
   {
      T ← T2 mod n
      if (T = ±1) return "a composite"
      if (T = −1) return "a prime"
   }
   return "a composite"
}

ex _i stsは、数値がミラーラビン検定に合格するたびに、それが素数ではない確率が1/4であることを証明します。数がm個のテストに合格した場合（m個の異なるパスを使用）、素数でない確率は（1/4） ^m です。 。

例 ：2進数を使用してミラーラビンアルゴリズムを適用し、341が合成数であるかどうかをテストします。

解決策 ：ミラーラビンアルゴリズムを使用して、次のように番号341をテストできます。

ステップ1：341 − 1 =2 ² x85。したがって、p =341、k=2およびq=85

ステップ2：x =2（与えられた）

ステップ3：S =x ^q mod p

=2 ⁸⁵ mod 341 =（2 ¹⁰ ）x 2 ⁵ mod 341 8

=2 ¹⁰ mod 341 x 2 ¹³ mod 341

=1 x 8192 mod 341 =8192 mod 341

=8

ステップ4：8≠1なので、次のステップに進みます。

ステップ5：j =1の場合、S =x ^2q mod p

=2 ¹⁷⁰ mod 341 =（2 ²⁰ ） ⁸ x 2 ¹⁰ mod 341

=2 ²⁰ mod 341 x 2 ⁸ mod 341 x 2 ¹⁰ mod 341

=1 x 256 x 1 =256

さて、=256≠1

結果は決定的ではありません

したがって、341は合成数ではありません。

利点

• このアルゴリズムを使用して、多数の素数性をテストできます。

• 他の素数性テストと比較した場合の速度の利点のため、ミラーラビンテストはいくつかの暗号化アプリケーションに最適なテストになります。

• オイラーおよびソロベイ-シュトラッセンのテストと比較すると、ミラーラビンはより動的であり、本質的な側面は失敗の可能性が減少することです。

• フェルマーの素数検定によると、すべてのカーマイケル数nに対して嘘つきが多すぎ、エラー確率は1に近く、この不利な点はミラーラビンで防止されています。