5

おそらく任意のビット長の素数を出力する関数 BigInteger.probablePrime(int bitLength, Random rnd) を認識しています。Java で REAL 素数が必要です。許容できるパフォーマンスでこれを行う FOSS ライブラリはありますか? 前もって感謝します!

編集:

私は 1024 と 2048 ビット素数を見ています。

4

5 に答える 5

10
  • 素数の可能性を使用して候補を生成する
  • AKS 素数性テストなどの高速な決定論的テストを使用して、候補が実際に素数であるかどうかを確認します。

編集:または、 isProbablePrime が十分に大きい確実性であると信頼できない場合はBigInteger(int bitLength, int certainty, Random rnd)、確実性のしきい値を調整できる BigInteger コンストラクターを使用します。

確実性 - 発信者が許容できる不確実性の尺度。新しい BigInteger が素数を表す確率は (1 - 1/2 の確実性) を超えます。このコンストラクターの実行時間は、このパラメーターの値に比例します。

暗号化の目的で使用される確率テストは、誤検知の確率を制限することが保証されています。こっそり通り抜ける落とし穴が存在するわけではなく、確率をどれだけ低くしたいかだけの問題です。Java BigInteger クラスがこれらを使用することを信頼できない場合 (どのテストが使用されたかが文書化されているとよいでしょう)、Rabin-Millerテストを使用してください。

于 2010-05-21T13:08:18.087 に答える
4

許容できるパフォーマンスで非常に大きな素数を生成する方法がいくつかありますが、ギネスブックに登録する以外のほとんどの目的には十分な密度ではありません。

これを次のように見てみましょう: によって返される数値probablePrime()が素数ではない可能性は、あなたやあなたが知っているすべての人が照明に当たる可能性よりも低くなります。2回。ある日。

心配しないでください。

于 2010-05-21T13:03:03.763 に答える
2

のコンストラクターを使用しBigIntegerて実素数を生成することもできます。

BigInteger(int bitLength, int certainty, Random rnd)

実行時間は確実性に比例しますが、私の Core i7 では問題ありません。

于 2012-09-03T19:07:45.007 に答える
1

メソッドを作成してラップします。

BigInteger definitePrime(int bits, Random rnd) {
    BigInteger prime = new BigInteger("4");
    while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
    return prime;
}
于 2010-05-21T12:57:08.517 に答える
0
Random rnd = new SecureRandom();
System.out.println(BigInteger.probablePrime(bitLength, rnd));

BigIntegerメソッドによって返されるが複合である確率は、probablePrime()2^-100 を超えません。

于 2013-11-26T02:14:20.603 に答える