なぜJavaでBigInteger.isProbablePrime（）関数が負の数に対してtrueを返すのですか？

Question

私は、JavaでRSA公開鍵暗号アルゴリズムを実装しています。 2つのランダムな素数を生成する必要があります。私は2048ビットのキーを作成するために2つの1024ビット数を生成するためにSecureRandomクラスを使用しています。私はBigIntegerクラスを使って数値を扱います。私はisProbablePrime（）関数を使って、それがプライムかどうかを100の確度で判断します。しかし、定義上、素数が負ではない場合でも、この関数が真の値を返すことに気付きました。

Answer 1

「なぜ」の質問に明確な回答を与えることはできません。そのためには、APIを設計した人と話をする必要があります。

私は@ westonの「それは問題ではない」との考えに同意する傾向があります。このlinkを参照してください。また、リンクからの別の持ち帰りは、に従うということです。素数が負であるかどうかは素数の定義が使用されています。 （もっとも広く使用されている定義ではありませんが...）

実装の動作はであることを熟考しています。このメソッドの実装は次のとおりです。

public boolean isProbablePrime(int certainty) { 
    if (certainty <= 0) 
     return true; 
    BigInteger w = this.abs(); 
    if (w.equals(TWO)) 
     return true; 
    if (!w.testBit(0) || w.equals(ONE)) 
     return false; 
    return w.primeToCertainty(certainty, null); 
} 

テストする前に候補の絶対値がどのようになるか注意してください。

この動作は（私が見ることができる）長い時間の間行われています。ZEROはJavaバグレポートを記録しました。これは@ westonの推測をサポートします。

---

かかわらずisProbablePrimeの行動が正しいかどうかの、実用的な解決策は、あなたの候補者がそれをテストする前に負であるかどうかを確認するためにテストを追加することです。

Answer 2

については、not matterを指摘しました。しかし、の内容はで、1024個のランダムビットを整数に変換するときは、どちらが正しい方法であるかを考慮する必要があります。それを署名付き（あなたのように）として扱うか、それを署名なしとして扱いますか？

例えば8ビットで、11010011をランダムに生成すると、211が素数である符号なし整数として扱われます。

符号付き整数として同じビット11010011を扱うと、負の素数を受け入れる場合でも、素数ではない-45が得られます。

これを間違って入力してください。コードが誤って有効なキーを除外し、無効なキーを誤って受け入れることになります。そして、すべてのネガティブを除外して安全な側に置くと、1023ビットの素数しか得られません（2の補数のネガティブは常に最上位ビットに1を持ちます）。

ビットから整数への変換を扱う方法では、ネガティブな素数の問題を避けることができ、RSAはキーとして選択された数を正しく解釈することができます。私のはと解釈され、その解釈は符号なしです。