最速素数性テスト

Question

多数の素数が素数であるかどうかをテストするために、実際に使用できる高速で決定論的な方法を提案できますか？

また、非決定的素数検査を正しく使用する方法を知りたいと思います。たとえば、私がそのようなメソッドを使用している場合、出力が「いいえ」の場合は数字が素数ではないことがわかりますが、出力が「おそらく」の場合はどうなりますか？この場合、素数を手動でテストする必要がありますか？

ありがとうございます。

Answer 1

私が知る素数検査のための決定論的多項式時間アルゴリズムは、AKS素数検査（http://en.wikipedia.org/wiki/AKS_primality_test）です。しかし、素早く成功する可能性が非常に高い非常に良い無作為化素数検定がたくさんあります。彼らは通常、数字が指数関数的に良い確率で合成されているかどうかを調べることによって動作するので、数字がコンポジットであると報告するか、非常に信頼できる「多分」と言う必要があります。

Answer 2

"おそらく"実際には1-εを意味し、εは必要なだけ小さくなります。

ほとんどのアプリケーションでは、確率を、例えば、暗号アプリケーションで

• 、幸いと秘密を推測攻撃、例えば、それに失敗するいくつかの小さなまだ非ゼロの確率が素数判定に接続されていない持って 2 ^（ - 100）

• ハードウェア障害（放射線）ランダムにコンピュータのメモリの一部のビットを反転（多分あなたの「決定論」素数判定の出力を保持しているものを

• バグ（不具合の他のタイプよりも実際に、多くの可能性）

だから大きさのその順番にεを押すと、実際には十分でしょう。

たとえば、OpenSSL、GnuPGは非決定的素数テストのみを使用します。 「おそらく、あなたは決定的なテストを本当に望んでいない。しかし、あなたが利用できるものを確認してください：手元に図書館があり、それが十分に実行されていれば、それを使ってください。

Answer 3

ランダムプライムをRSAキーで使用する場合は、まず確率テストを使用する必要があります。確率があなたのニーズに十分に高い場合は、そこで停止します。あなたが確かなものでなければならない場合は、大規模な確率の高い素数を見つけたら、AKSなどの確率的でないテストでそれを検証します。これにより、素数以外の素数を素早くチェックすることができます。

特定の既存の番号がプライムであることを確認しようとする場合は、確実に答えているテストの1つを使用する必要があります。他の非多項式時間テストもありますが、実際には最も速いものを使用してください。