Subversion Repositories Code-Repo

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
219 Kevin 1 
import math
2 
 
3 
def Extended_Euclidian(a, b):
4 
	''' Takes values a and b and returns a tuple (r,s,t) in the following format:
5 
		r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
6 
	t_ = 0
7 
	t = 1
8 
	s_ = 1
9 
	s = 0
10 
	q = a//b
11 
	r = a - q * b
12 
	# print("%d\t= %d * %d + %d" % (a, q, b, r))
13 
	while r > 0:
14 
		temp = t_ - q * t
15 
		t_ = t
16 
		t = temp
17 
		temp = s_ - q * s
18 
		s_ = s
19 
		s = temp
20 
		a = b
21 
		b = r
22 
		q = a//b
23 
		r = a - q * b
24 
		# print("%d\t= %d * %d + %d" % (a, q, b, r))
25 
	r = b
26 
	return (r, s, t)
27 
 
28 
def Inverse(a, b):
29 
	'''Returns the multiplicative inverse of a mod b'''
30 
	ret = Extended_Euclidian(a,b)
31 
	if (ret[1] < 0):
32 
		inv = ret[1] + b
33 
	else:
34 
		inv = ret[1]
35 
	return inv
36 
 
37 
def GCD(q,N):
38 
	'''Returns the GCD of a and b'''
39 
	ret = Extended_Euclidian(q,N)
40 
	return ret[0]
41 
 
42 
def PollardRhoLog(G,p,n,alpha,beta):
43 
	'''Implements the Pollard Rho discrete log factoring algorithm'''
44 
	def PollardRhoFunction(x,a,b):
45 
		'''Helper functions for defining sets'''
46 
		if x % 3 == 1:
47 
			return (beta*x%p,a,(b+1)%n)
48 
		elif x % 3 == 0:
49 
			return (x**2%p,2*a%n,2*b%n)
50 
		else:
51 
			return (alpha*x%p,(a+1)%n,b)
52 
 
53 
	i = 1
54 
	(x,a,b) = PollardRhoFunction(G[0],G[1],G[2])
55 
	(x_,a_,b_) = PollardRhoFunction(x,a,b)
56 
	print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_))
57 
 
58 
	while x != x_:
59 
		i += 1
60 
		(x,a,b) = PollardRhoFunction(x,a,b)
61 
		(x_,a_,b_) = PollardRhoFunction(x_,a_,b_)
62 
		(x_,a_,b_) = PollardRhoFunction(x_,a_,b_)
63 
		print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_))
64 
	if GCD(b_-b,n) != 1:
65 
		return -1
66 
	else:
67 
		return (a-a_)*Inverse((b_-b), n)%n
68 
 
69 
 
70 
if __name__ == '__main__':
71 
	print(PollardRhoLog((1,0,0),526483,87747,13,59480))