java - Javaで160ビットの素数を生成するにはどうすればよいですか?

Question

Java で 160 ビットの素数を生成したいと考えています。すべての 160 ビット数値をループ処理する必要があることはわかっています。任意の数値 についてn、それらが 未満の素数sqroot(n)または のような素数テストによって割り切れるかどうかを確認する必要がありますMiller-Rabin test。私の質問は次のとおりです。

1. これを行う特定のライブラリはありますか?

2. これを行う他の（より良い）方法はありますか？

Answer 1

BigInteger.probablePrime(160, new Random())BigIntegerは、ほぼ確実に素数である を生成します。これが素数ではない確率は、雷に打たれる確率よりも低くなります。一般に、BigInteger十分にテストされ、最適化された素数性テスト操作が組み込まれています。

価値があるのは、これが永遠にかからない理由は、素数定理により、ランダムに選択された n ビット数が素数の 1/n に比例する確率を持つため、平均して O(n )素数を見つける前に、さまざまなランダムなnビット数。