Shanks

16 hours ago by bcr49

This illustrates the Baby-Step Giant-Step Algorithm

p = next_prime(73) F = GF(p) a = F(primitive_root(p)) b = 9 # We will compute log_a(b) using Baby-step Giant-step m = ceil(sqrt(p-1)) L1 = [] L2 = [] ak = 1 am = a^-m abk = b for i in range(m) : L1.append(ak) L2.append(abk) ak = ak*a abk = abk*am print L1 print L2 #The following function searches for a match in the two lists and returns the corresponding indicies. def find_matching_index(list1, list2): inverse_index = { element: index for index, element in enumerate(list1) } return [(inverse_index[element],index) for index, element in enumerate(list2) if element in inverse_index] match = find_matching_index(L1, L2) print "we have a match for the indicies", [ match[0][0],match[0][1] ] q = match[0][1] r = match[0][0] x = m*q+r # This is our solution to x = log_a(b) x print a a^x == b