Java BigInteger Primzahlen

Question

Ich versuche, eine zufällige Primzahl des Typs BigInteger zu erzeugen, dass zwischen einem minimalen und maximalen Wert ist, die ich liefern.

Ich bin mir der BigInteger.probablePrime (int Bitlänge, random), aber ich bin nicht sicher, wie oder, selbst wenn die Bitlänge übersetzt in eine max / min-Wert des ausgegebenen Primzahl ist.

Danke, Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random) wird eine (wahrscheinlich) prime des angegebenen Bitlänge zurückzukehren. Das führt zu einem maximalen Wert von 2 ^ Bitlänge - 1 und ein Minimum von 2 ^ (Bitlänge - 1). So viel wie ich es als Antwort hasse, es ist wahrscheinlich die beste Wahl, wenn Sie Eintauchen in der Zahlentheorie beginnen sollen.

Was würden Sie das Bit herauszufinden tun müssen, ist Längen, dass Ihr Bereich fordert, dann um sie vorbei probablePrime(), bis Sie wieder eine erstklassige bekommen, die im rechten Bereich ist.

Answer 2

jprete Antwort ist in Ordnung, wenn Ihr Verhältnis max / min ist nicht auf 1 schließen.

Wenn Sie einen engen Bereich haben, ist Ihre beste Wette ist wahrscheinlich nur so etwas wie die folgenden Funktionen ausführen:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

Die Dichte Primzahlen ziemlich hohen Gesamt ist, ist es im Grunde 1 in log (x) ist, so dass Sie nicht zu oft zu wiederholen, sollte eine Primzahl zu finden. (Nur als Beispiel: Zahlen rund 10 ²³ , ein in all 52 Zahlen im Durchschnitt eine Primzahl Der obige Code stört nur bei 2 von jeweils 6 Zahlen, so dass Sie am Ende würden. einen Durchschnitt von 17-mal für Zahlen Umschlingung 10 ²³ .)

So stellen Sie sicher, dass Sie haben einen guten Primzahltest und die Java BigInteger hat eine.

Als Übung für den Leser, die obige Funktion erweitern, so dass es mehr zusammengesetzte Zahlen filtert vor der Zeit von 30k mit + x (Modulo 30 gibt es 22 Module, die immer zusammengesetzte sind, nur 8 verbleibenden dass prime sein könnte) oder 210k + x.

edit: siehe auch US Patent # 7.149.763 (OMFG !!!)