Speicherfehler in Python Primtests Programm

Question

def wiederholt (m, Ergebnis, a, s, d):

check = True 
r = 0 
while r <= s - 1: 
    if result == m - 1: 
     check = False 
     return check 
    result = (result ** 2) % m 
    r = r + 1 
return check 

Ich brauche ein Primtests Python-Programm zu schreiben, sehr große Zahlen zu testen, wie mindestens 100 -Zifferzahlen. Der obige Code ist Teil des Codes für den deterministischen Miller-Rabin-Primzahltest für wiederholtes Quadrieren. Es funktioniert sehr langsam für große Zahlen. Wie kann ich es beschleunigen? Es ist für ein Projekt. Vielen Dank!

Answer 1

Ihr Problem ist wahrscheinlich die (result ** 2) % m, verwenden Sie die 3 Argument Version von pow, die das gleiche tun, aber effizienter, da der Algorithmus Verwendung der Modular exponentiation ist, und das ist viel besser als die erste x**n tun und dann seine Modulo berechnen. Auf diese Weise können Garantie sind nie eine Nummer größer als m haben, während, wenn Sie (x**n) % m tun können Sie haben, dass x**n ist sehr viel größer als m, dass die Ursache Ihrer Probleme

auch keine Notwendigkeit für die check Variable und Sie don können verwende nicht a. auch, wie Sie von 0 bis s-1 gehen, eine bessere Nutzung Bereich

def repeated(m, result, s, d): 
    for r in range(s): 
     if result == m - 1: 
      return False 
     result = pow(result, 2, m) 
    return True 

nun für diesen Teil der test

wenn

Sie brauchen a, d, s und n diese ist, wie ich es tun würde

def mr_check(n,a,s,d): 
    result = pow(a,d,n) 
    if result == 1 : 
     return False 
    for r in range(s): 
     result = pow(result,2,n) 
     if result == n-1: 
      return False 
    return True