Primalitätstest dauert länger als Brute-Force-Methode, wie kann ich verbessern?

Question

Ich versuche, Primzahlen auf einer einzigen Maschine zu berechnen, in der Größenordnung von 2^30-2^100.
Mein Algorithmus ist unten für jeden Interessierten enthalten.
Ich habe das Python-Code optimiert zu werden O(sqrt(n/2)) (glaube ich) für jede Zahl: es akzeptiert nur ungerade Zahlen, und ich sicher, die Zahl übergeben, um es seltsam in einem anderen Verfahren ist.

Ich habe die Fermat Primality Test zu versuchen und beschleunigen den Prozess. Allerdings sind die Zahlen zu groß für die eingebaute math.pow() Methode, so dass ich Exponentiation durch Squaring verwendet habe.
Dies erfordert jedoch eine sehr lange Zeit für größere Zahlen - die mit roher Gewalt schneller wären.

Ist meine Implementierung falsch?
Die Zeit kommt vom Quadrierungsalgorithmus, sein Wiederholungsstapel verschlingt auch mein Gedächtnis, gibt es einen schnelleren Algorithmus dafür, den ich erforschen sollte?

Um zu berechnen, ob die Nummer 35184372088967 prime ist, dauerte es .00100111 Sekunden mit meinem Brute-Force-Algorithmus, aber dauerte 0,4608 Sekunden, um den Prime-Test zu starten.

Brute-Force-Primzahl-Check:

def isPrime(n): 
    for i in range(3,int(math.sqrt(n)),2): 
     if(n%i==0): 
      return False 
    return True 

Implementierung von Fermat-Algorithmus:

def couldBePrime(n): 
     if(n>308): 
      return power(2,n-1)%n==1 
     else: 
      return math.pow(2,n-1)%n==1 

Potenzierung durch Algorithmus quadriert (Der zeitraubende Teil):

def power(base,exp): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base 
    elif (exp & 1) != 0: 
     return base * power(base * base, exp // 2) 
    else: 
     return power(base * base, exp // 2) 

Answer 1

Bug : math.pow berechnet Gleitkommawerte. Fließkommaberechnungen sind Näherungswerte und liefern Ihnen hier bedeutungslose Ergebnisse. Sie benötigen Integer-Berechnungen, wie Sie sie (ineffizient) in Ihrer power Funktion machen. Pythons eingebauter **-Operator und pow-Funktion (nicht math.pow, die eine andere Funktion ist) arbeiten beide auf Ganzzahlen.

In Python, wie in vielen Programmiersprachen, ist die Bibliothek math speziell über Fließkommaberechnungen, nicht über andere Arten von mathematischen Berechnungen wie Berechnungen in ganzen Zahlen.

Ineffizienz: Um b^e mod n zu berechnen, ist es viel effizienter, arithmetische Modulo n durchzuführen, als zuerst b^e zu berechnen und dann das Ergebnis durch n zu teilen. Die Berechnung von b erfordert die Bildung einer sehr großen Zahl, und dies wird langsam sein, da die Zahlen ziemlich schnell groß werden, wenn die Berechnung höhere und höhere Kräfte von b durchläuft. (Der optimale Weg zur Berechnung von b^e ist nicht leicht zu bestimmen, aber alle Wege beinhalten die Berechnung der mittleren Kräfte von b, die einzige praktische Ungewissheit ist in welcher Reihenfolge.) Wenn Sie das Ergebnis modulo n wollen, machen Sie alle aufeinanderfolgenden Multiplikationen modulo n: Berechne b^2 mod n, dann quadratisch und reduziere modulo n, um b^4 mod n usw. zu erhalten. Jedesmal, wenn du eine Multiplikation machst, nimmst du den Rest der Division mit n, bevor du etwas anderes machst.

In Python die Standard-Library-Funktion pow (denken Sie daran, nichtmath.pow) wird das für Sie tun.Es ist so einfach wie

def couldBePrime(n): 
    return pow(2, n-1, n) == 1 

Wenn Python diese Funktion nicht hat, dann Ihre power Funktion eine vernünftige Art und Weise zu implementieren, wenn Sie jedes Zwischenergebnis Modulo n reduziert.

def power(base, exp, mod): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base % mod 
    elif (exp & 1) != 0: 
     return (base * power((base * base) % mod, exp // 2, mod)) % mod 
    else: 
     return power((base * base) % mod, exp // 2) 

eine eingebaute Funktion aufrufe ist viel schneller, natürlich beide, denn dies ist ein ordentlicher, aber nicht extrem guter Weg, um die Operation auszuführen, und weil Python mehr für eine einfache Schreib optimiert ist als für Geschwindigkeit Daher ist es das Beste, das so viel wie möglich des numerischen Schwergewichts zu den eingebauten Funktionen zu lassen.

Eine zusätzliche Anmerkung: um eine Potenz von zwei zu berechnen, gibt es einen viel schnelleren Weg als Multiplikationen - do bit shifting. Aber das hilft hier nicht, weil Sie 2^e mod n und nicht 2^e berechnen wollen.