情報セキュリティにおける素数性テストとは何ですか？

素数性テストは、入力数が素数であるかどうかを判断するためのアルゴリズムです。一部の素数性テストは決定論的です。数が素数か合成数かを常に正しく判断します。

最速の既知の決定論的素数性テストは2004年に発明されました。Agrawal、Kayal、Saxenaなどの3人のコンピューター科学者が、O〜（log（n） ⁶ で動作するAKS素数性テストを発明しました。 ）時間。ここで、O〜（f（n））はO（f（n）.log（f（n）） ^k として表されます。 ）ある整数k[1]の場合。大きな進歩ですが、情報セキュリティ要件と比較すると、この速度はかなり遅いです。

素数の利点は、暗号化で利用されることです。標準の暗号システム-RSAアルゴリズムの1つは、より高いセキュリティを提供するために、通常1024ビットを超える素数をキーとして必要とします。

このような大きな数で処理する場合、次のメソッドは絶対にうまく作成されません。特に、実行される操作が素数性テストの時点で/および％である場合は、このような多数を処理するだけではありません。

したがって、生成される最良の素数判定アルゴリズムは、提供された数が「確率的素数」であるか合成数であるかを判断することしかできません。

次のような素数判定の種類があります-

• 決定論的アルゴリズム −決定論的素数性テストアルゴリズムは整数を受け入れ、素数または合成数を継続的に出力します。このアルゴリズムは常に適切な答えを提供します。

• 除算アルゴリズム −最も単純な素数性テストは次のとおりです-

  入力番号nが与えられると、2からn-1までの整数がnを除算するかどうかをチェックします。 nが任意のmで割り切れる場合、nは合成数であり、それ以外の場合は素数です。ただし、n – 1までのすべてのmをテストする代わりに、√nまでのmをテストすることだけが重要です。 nが合成数の場合、nitは2つの値に因数分解でき、そのうちの少なくとも1つは√n以下である必要があります。

• 確率的アルゴリズム −確率的アルゴリズムは、ほとんどの場合正しい答えを提供しますが、常に正しいとは限りません。これらのテストは、nがすべての素数が満たすべき1つ以上の条件を満たすかどうかを決定しました。確率的アルゴリズムは、素数または合成のいずれかを復元しますが、次のルールに依存します-

  • テストする整数が実際に素数である場合、アルゴリズムは間違いなく素数を返します。

  • テストする整数が実際にコンポジットである場合、確率1 −εのコンポジットを返しますが、確率εの素数を返すことができます。アルゴリズムを「m」回実行でき、エラーの確率がΣ ^m に減少する場合、ミスの確率を高めることができます。 。

フェルマーの素数性テスト −フェルマーの素数性テストは、フェルマーの小定理に基づいています。この定理では、nが素数の場合、a ^n-1 ≡1（mod n）。入力nとa n-1 かどうかをチェックできます。 ≡1（mod n）。これが当てはまらない場合、nは合成数であり、nはおそらく素数です。残念ながら、フェルマーの素数性テストにはエラーのコストが高く、おそらくプライムであるコンポジットが多すぎます。