When $ x = a ^ k $, the square calculation is performed $ k $ times. The binary method is a method to reduce the amount of calculation to $ log (k) $ by sequentially finding $ a ^ {2 ^ i} $ as a method to make the calculation efficient.
The calculation is executed by expanding to a binary number and expanding in order from the left. As a result, $ g ^ k (mod p) $ is calculated.
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