Generiere große Primzahl mit den angegebenen letzten Ziffern

Question

Frage mich, wie es möglich ist, 512 Bit (155 Dezimalziffern) Primzahl zu erzeugen, von denen die letzten fünf Dezimalziffern spezifiziert/festgelegt sind (zB *** 28071) ??

Die Prinzipien der Erzeugung einfacher Primzahlen ohne Spezifikationen sind durchaus verständlich, aber mein Fall geht weiter.

Irgendwelche Hinweise für, wo soll ich anfangen?

Java oder C# ist vorzuziehen.

Danke!

Answer 1

Ich denke, der einzige Weg, um eine Zufallszahl von 150 Dezimalstellen erste erzeugen würde, dann die 28071 dahinter anhängen von number = randomnumber * 100000 + 28071 tun dann nur Brute-Force mit etwas aus wie

while (!IsPrime(number)) 
    number += 100000; 

Natürlich diesem könnte eine Weile dauern, um zu berechnen ;-)

Answer 2

Haben Sie versucht, nur solche Zahlen zu generieren und sie zu überprüfen? Ich würde erwarten, dass das akzeptabel schnell ist. Die Primzahldichte nimmt nur als Logarithmus der Zahl ab, also würde ich erwarten, dass Sie ein paar hundert Zahlen versuchen, bis Sie eine Primzahl treffen. ln(2^512) = 354 so wird etwa eine Nummer in 350 Prime sein.

Grob gesagt, das Primzahl-Theorem besagt, dass, wenn eine Zufallszahl in der Nähe einig große Zahl N ausgewählt ist, die Chance, es prime zu sein, ist etwa 1/ln (N), wobei ln (N) bezeichnet die natürlichen Logarithmus von N. Zum Beispiel, in der Nähe von N = 10.000, ist etwa eine von neun Zahlen Primzahl, während in der Nähe von N = 1.000.000.000 nur eine von 21 Zahlen Primzahl ist. Mit anderen Worten, ist der durchschnittliche Abstand zwischen Primzahlen in der Nähe von N ungefähr ln (N)

(von http://en.wikipedia.org/wiki/Prime_number_theorem)

Sie müssen nur darauf achten, dass eine Nummer für Ihre Endziffern existiert. Aber ich denke, das ist so einfach wie zu überprüfen, dass die letzte Ziffer nicht durch 2 oder 5 teilbar ist (d. H. Es ist 1, 3, 7 oder 9).

Nach this performance data können Sie etwa 2000 ModPow Operationen auf 512-Bit-Daten pro Sekunde tun, und da ein einfacher Prime-Test wird 2^(p-1) mod p=1 Überprüfung, die den Betrieb eine ModPow ist, sollten Sie in der Lage sein, pro Sekunde mehr Primzahlen mit Eigenschaften zu erzeugen, .

So könnte man tun (Pseudo-Code):

BigInteger FindPrimeCandidate(int lastDigits) 
{ 
    BigInteger i=Random512BitInt; 
    int remainder = i % 100000; 
    int increment = lastDigits-remainder; 
    i += increment; 
    BigInteger test = BigInteger.ModPow(2, i - 1, i); 
    if(test == 1) 
     return i; 
    else 
     return null; 
} 

Und tun umfangreichere prime Kontrollen auf das Ergebnis dieser Funktion.

Answer 3

Sie könnten einen der standard methods for generating large primes erweitern, indem Sie eine zusätzliche Einschränkung hinzufügen, d. H. Dass die letzten 5 Dezimalziffern korrekt sein müssen. Naiv, Sie können dies einfach als einen zusätzlichen Test hinzufügen, aber es wird die Zeit erhöhen, um eine geeignete Primzahl durch 10^5 zu finden.

Nicht so naiv: Erzeuge eine zufällige 512-Bit-Zahl und setze dann genügend niederwertige Bits, so dass die Dezimaldarstellung mit der erforderlichen Sequenz endet. Fahren Sie dann mit den normalen Primzahltests fort.

Answer 4

Betrachten wir Brute-Force.Werfen Sie einen Blick auf diesen sehr interessanten Text „Die Primzahl Lotterie“ genannt:

• http://plus.maths.org/content/prime-number-lottery

der letzte Eintrag in der letzten Tabelle gibt es ~ 2,79 * 10^14 Primzahlen weniger als 10^16. Somit ist ungefähr jede 35. Zahl eine Primzahl in diesem Bereich.

EDIT: Siehe den Kommentar von CodeInChaos - wenn Sie nur ein paar tausend 512-Bit-Nummern mit den letzten 5 Ziffern gehen, werden Sie schnell einen finden.

Answer 5

Wie @Doggot sagte, aber Start von mindestens 150 stellige Nummer, die mit 28071 endet, bedeutet 100000 .... 0028071, jetzt addieren Sie es mit 100000 jedes Mal und zum Testen verwenden Sie in erster Linie Miller Rabin wie der Code, den ich zur Verfügung gestellt here, braucht es einige Anpassungen. Wenn der Rückgabewert wahr ist, überprüfen Sie ihn hauptsächlich auf Genauigkeit.

Answer 6

Sie können ein Sieb verwenden, das nur Zahlen enthält, die Ihre spezielle Bedingung erfüllen, um durch kleine Primzahlen teilbare Zahlen herauszufiltern.

Für jede kleine Primzahl p müssen Sie den richtigen Startpunkt und Schritt finden, indem Sie berücksichtigen, dass nur jede 100000ste Zahl im Sieb vorhanden ist.

Für die Zahlen, die das Sieb überleben, können Sie BigInteger.isProbablePrime() verwenden, um zu überprüfen, ob es mit ausreichender Wahrscheinlichkeit prim ist.

Answer 7

schrieb ich den Brute-Force-Algorithmus aus der int Welt zum BigDecimal man mit Hilfe der BigSquareRoot Klasse von http://www.merriampark.com/bigsqrt.htm. (Beachte, dass von 1 bis 1000 genau 168 Primzahlen angegeben werden.)

Entschuldigung, aber wenn Sie dort Ihren Bereich angeben, d. H. ; 10 -1>, Sie können Ihren Computer arbeiten lassen und wenn Sie im Ruhestand sind, können Sie das Ergebnis haben ... es ist verdammt langsam!

Allerdings kann man zumindest einen Teil davon nützlich finden in Kombination mit den anderen Antworten in diesem Thread.

 

package edu.eli.test.primes; 

import java.math.BigDecimal; 

public class PrimeNumbersGenerator { 

    public static void main(String[] args) { 
// BigDecimal lowerLimit = BigDecimal.valueOf(10).pow(154); /* 155 digits */ 
// BigDecimal upperLimit = BigDecimal.valueOf(10).pow(155).subtract(BigDecimal.ONE); 

    BigDecimal lowerLimit = BigDecimal.ONE; 
    BigDecimal upperLimit = new BigDecimal("1000"); 

    BigDecimal prime = lowerLimit; 
    int i = 1; 

    /* http://www.merriampark.com/bigsqrt.htm */ 
    BigSquareRoot bsr = new BigSquareRoot(); 
    upperLimit = upperLimit.add(BigDecimal.ONE); 
    while (prime.compareTo(upperLimit) == -1) { 

     bsr.setScale(0); 
     BigDecimal roundedSqrt = bsr.get(prime); 

     boolean isPrimeNumber = false; 
     BigDecimal upper = roundedSqrt; 
     while (upper.compareTo(BigDecimal.ONE) == 1) { 

     BigDecimal div = prime.remainder(upper); 
     if ((prime.compareTo(upper) != 0) && (div.compareTo(BigDecimal.ZERO) == 0)) { 
      isPrimeNumber = false; 
      break; 
     } else if (!isPrimeNumber) { 
      isPrimeNumber = true; 
     } 

     upper = upper.subtract(BigDecimal.ONE); 
     } 

     if (isPrimeNumber) { 
     System.out.println("\n" + i + " -> " + prime + " is a prime!"); 
     i++; 
     } else { 
     System.out.print("."); 
     } 
     prime = prime.add(BigDecimal.ONE); 
    } 
    } 

} 
 

Answer 8

Lassen Sie ABCDE die fünfstellige Nummer in der Basis zehn, die Sie in Betracht ziehen. Basiert auf Dirichlet's theorem on arithmetic progressions, wenn ABCDE und 100000 Koprime sind, dann gibt es unendlich viele Primzahlen der Form 100000 * k + ABCDE. Da Sie nach Primzahlen suchen, teilen weder 2 noch 5 ABCDE, daher sind ABCDE und 100000 nur Koprime. So gibt es unendlich viele Primzahlen der Form, die Sie in Betracht ziehen.