Wenn $ x = a ^ k $ ist, wird die Quadratberechnung $ k $ mal durchgeführt. Um die Berechnung effizienter zu gestalten, besteht die binäre Methode darin, den Rechenaufwand auf $ log (k) $ zu beschränken, indem $ a ^ {2 ^ i} $ nacheinander ermittelt wird.
Die Berechnung wird ausgeführt, indem auf eine Binärzahl erweitert und in der Reihenfolge von links erweitert wird. Als Ergebnis wird $ g ^ k (mod p) $ berechnet.
binary.py
def Binary(k, g, p):
k_binary = []
while(k != 0):
k_binary.append(k%2)
k = k//2
if k == 1:
k_binary.append(k)
k = 0
y = 1
for i in reversed(range(len(k_binary))):
if k_binary[i] == 1:
y = (y*y%p)*g%p
else:
y = (y*y%p)
return y
Recommended Posts