Subversion Repositories Code-Repo

import math

def Extended_Euclidian(a, b):

	''' Takes values a and b and returns a tuple (r,s,t) in the following format:

		r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''

	t_ = 0

	t = 1

	s_ = 1

	s = 0

	q = a//b

	r = a - q * b

	# print("%d\t= %d * %d + %d" % (a, q, b, r))

	while r > 0:

		temp = t_ - q * t

		t_ = t

		t = temp

		temp = s_ - q * s

		s_ = s

		s = temp

		a = b

		b = r

		q = a//b

		r = a - q * b

		# print("%d\t= %d * %d + %d" % (a, q, b, r))

	r = b

	return (r, s, t)

def Inverse(a, b):

	'''Returns the multiplicative inverse of a mod b'''

	ret = Extended_Euclidian(a,b)

	if (ret[1] < 0):

		inv = ret[1] + b

	else:

		inv = ret[1]

	return inv

def Shanks(n,a,b):

	''' Implements the Shanks algorithm for solving the Discrete Logarithm Problem'''

	m = math.ceil(math.sqrt(n))

	d = a**m % n

	# Generate and sort list L1

	L1 = dict()

	for i in range(m):

		L1[i] = d**i % n

	print('L1: (unsorted)')

	for i in range(m):

		print("%d\t:\t%d" % (i, L1[i]))

	L1 = sorted(L1.items(), key=lambda x: x[1])

	# Generate and sort list L2

	L2 = dict()

	for i in range(m):

		L2[i] = b * Inverse(a**i, n) % n

	print('L2: (unsorted)')

	for i in range(m):

		print("%d\t:\t%d" % (i, L2[i]))

	L2 = sorted(L2.items(), key=lambda x: x[1])

	# Search for a pair with identical second coordinates

	for e in L1:

		for f in L2:

			if e[1] == f[1]:

				j = e[0]

				k = f[0]

				break;

	return m * j + k % n

if __name__ == '__main__':

	# a = 2

	# b = 767

	# n = 526483

	# d = Shanks(n, a, b)

	# print(d)

	# a = 2

	# b = 48

	# n = 101

	# d = Shanks(n, a, b)

	# print(d)

	# a = 2

	# b = (48**27)*(27**33)

	# n = 101

	# d = Shanks(n, a, b)

	# print(d)

	a = 2

	b = 19

	n = 4481

	d = Shanks(n, a, b)

	print(d)