Lorsque $ x = a ^ k $, le calcul du carré est effectué $ k $ fois. Pour rendre le calcul efficace, la méthode binaire consiste à limiter le montant du calcul à $ log (k) $ en trouvant séquentiellement $ a ^ {2 ^ i} $.
Le calcul est exécuté en développant un nombre binaire et en développant dans l'ordre à partir de la gauche. En conséquence, $ g ^ k (mod p) $ est calculé.
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