Schnelle modulare Exponentiation, hilf mir den Fehler zu finden

Question

Ich versuche ein Schema der schnellen Exponentiation zu implementieren. Grad in binärer Form dargestellt:

def pow_h(base, degree, module): 
    degree = bin(degree)[2:] 
    r = 1 

    for i in range(len(degree) - 1, -1, -1): 
     r = (r ** 2) % module 
     r = (r * base ** int(degree[i])) % module 

    return r 

Aber Funktion funktioniert nicht richtig, wo ist der Fehler?

Answer 1

Wie ich in den Kommentaren sagte, die eingebaute pow Funktion macht bereits schnelle modulare Exponentiation, aber ich denke, es ist eine vernünftige Kodierung Übung, um es selbst zu implementieren.

Ihr Algorithmus ist in der Nähe, aber Sie tun das Falsche. Sie müssen das Quadrat base, nicht r, und Sie sollten es nach dem Multiplikationsschritt tun.

def pow_h(base, degree, module): 
    degree = bin(degree)[2:] 
    r = 1 
    for i in range(len(degree) - 1, -1, -1): 
     r = (r * base ** int(degree[i])) % module 
     base = (base ** 2) % module 
    return r 

#test 

for i in range(16): 
    print(i, 2**i, pow_h(2, i, 100)) 

Ausgang

0 1 1 
1 2 2 
2 4 4 
3 8 8 
4 16 16 
5 32 32 
6 64 64 
7 128 28 
8 256 56 
9 512 12 
10 1024 24 
11 2048 48 
12 4096 96 
13 8192 92 
14 16384 84 
15 32768 68 

r * base ** int(degree[i]) Verwendung ist ein netter Trick, aber es ist wahrscheinlich effizienter, eine if Aussage als Potenzierung zu verwenden. Und Sie können Arithmetik verwenden, um die Bits von degree zu erhalten, anstatt String zu verwenden, obwohl bin ziemlich effizient ist. Wie auch immer, hier ist meine Version:

Answer 2

Eine solche schnelle Potenzierung muss anders handeln, wenn der aktuelle Exponent gerade oder ungerade ist, aber Sie haben keine solche Überprüfung in Ihrem Code. Hier einige Hinweise:

Um x**y zu finden, benötigen Sie eine "Akkumulator" Variable, um den bisher berechneten Wert zu halten. Lassen Sie uns a verwenden. So finden Sie a*(x**y), mit Ihrem Code abnehmende y und steigende a und/oder x bis y wird Null und a ist Ihre endgültige Antwort.

Wenn y gerade ist, sagen Sie y==2*k, dann a*x**(2*k) == a*(x**2)**k. Dies verringerte y zu y//2 und erhöhte x zu x**2. Wenn die y ungerade ist, sagen Sie y==2k+1, dann a*x**(2*k+1) == (a*x)*x**(2*k). Dies verringerte y zu y-1 und erhöhte a zu a*x.

Sie sollten in der Lage sein, den Algorithmus von hier aus zu berechnen. Ich habe den Modul nicht mit einbezogen: Das sollte einfach sein.