Warum gibt die Funktion BigInteger.isProbablePrime() in Java für negative Zahlen den Wert true zurück?

Question

Ich implementiere den RSA Public-Key-Verschlüsselungsalgorithmus in Java. Es erfordert zwei zufällige Primzahlen zu generieren. Ich habe die SecureRandom-Klasse verwendet, um zwei 1024-Bit-Nummern zu generieren, um einen 2048-Bit-Schlüssel zu erstellen. Ich verarbeite die Zahlen mit der BigInteger-Klasse. Ich benutze die isProbablePrime() - Funktion, um zu bestimmen, ob es prim ist, mit einer Sicherheit von 100. Ich habe jedoch festgestellt, dass diese Funktion für negative Zahlen wahr ist, obwohl die Primzahlen definitionsgemäß nicht negativ sein können.

Answer 1

Wir können Ihnen keine definitive Antwort auf die Frage "Warum" geben. Dafür müssten Sie mit den Leuten sprechen, die die API entworfen haben.

Ich bin geneigt zu stimmen mit @ Weston Vermutung, dass "es keine Rolle spielt"; siehe hierzu link. Und noch ein Mitnehmen von der Verbindung ist, dass es auf ankommt, die Definition der Primzahl wird verwendet, ob Primzahlen negativ sind. (Durch die am weitesten verbreitete Definition sind sie nicht, aber ...)

Allerdings kann ich Ihnen sagen, dass die Implementierung Verhalten ist absichtlich. Die Implementierung der Methode ist wie folgt:

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); 
} 

Beachten Sie, wie es den absoluten Wert des Kandidaten vor dem Test benötigt.

Dieses Verhalten ist seit langer Zeit mit (von dem, was ich sehen kann) ZERO aufgezeichnet Java Bug Reports darüber. Dies unterstützt @ Westons Vermutung.

---

Unabhängig davon, ob isProbablePrime ‚s Verhalten richtig ist, ist die pragmatische Lösung, die einen Test, um zu sehen, wenn Ihr Kandidat vor dem Test negativ hinzuzufügen ist.

Answer 2

Auf Primzahlen, wies ich darauf hin, dass es not matter. Aber was spielt eine Rolle ist, wenn Sie die 1024 zufälligen Bits in eine ganze Zahl konvertieren, müssen Sie überlegen, welche der richtige Ansatz ist; behandle es als unterzeichnet (wie du bist) oder behandle es unsigniert?

Also zum Beispiel in 8 Bits, wenn ich zufällig 11010011 das 211 erzeugt, wenn es als vorzeichenlose ganze Zahl behandelt wird, die eine Primzahl ist.

Wenn ich die gleichen Bits 11010011 als eine vorzeichenbehaftete Ganzzahl behandeln, bekomme ich -45, die kein Prime ist, auch wenn Sie negative Primzahlen akzeptieren.

Falsch und Ihr Code wird fälschlicherweise gültige Schlüssel ausschließen und ungültige Schlüssel fälschlicherweise akzeptieren. Und wenn Sie alle Negative ausschließen, nur um auf der sicheren Seite zu sein, dann werden Sie nur 1023 Bit-Primzahlen bekommen (Zweierkomplement-Negative haben immer eine 1 im höchstwertigen Bit).

So die Art, wie Sie mit der Umwandlung von Bits zu Integer umgehen, ist in der Lage, Negative zu vermeiden und die ganze Frage negativer Primzahlen zu vermeiden, und RSA würde nur eine korrekte Interpretation der als Schlüssel ausgewählten Zahl haben. Meine Schätzung ist, dass die Interpretation nicht signiert ist.