Baby Step Giant Step Algorithm Python Code
#Baby Step Giant Step DLP problem y = a**x mod n
#Example 70 = 2**x mod 131
y = 70
a = 2
n = 131
s = floor(sqrt(n))
A = []
B = []
for r in range(0,s):
value = y*(a^r) % n
A.append(value)
for t in range(1,s+1):
value = a^(t*s) % n
B.append(value)
print A
print B
x1,x2 =0,0
for r in A:
for t in B:
if r == t:
x1 = A.index(r)
x2 = B.index(t)
print x1,x2
break
print 'the value of x is ', ((x2+1)*s - x1) % n # Answer
This comment has been removed by the author.
ReplyDeleteThere is no need to store list B, you also have some python mistakes: ^ should be **, s needs to be cast to int
ReplyDeleteI'd write it like this:
def baby_step_giant_step(y, a, n):
...s = int(ceil(sqrt(n)))
...A = [y * pow(a, r, n) % n for r in xrange(s)]
...for t in xrange(1,s+1):
......value = pow(a, t*s, n)
......if value in A:
......return (t * s - A.index(value)) % n