| 0,0 → 1,71 |
|---|
| 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 GCD(q,N): |
| '''Returns the GCD of a and b''' |
| ret = Extended_Euclidian(q,N) |
| return ret[0] |
| |
| def PollardRhoLog(G,p,n,alpha,beta): |
| '''Implements the Pollard Rho discrete log factoring algorithm''' |
| def PollardRhoFunction(x,a,b): |
| '''Helper functions for defining sets''' |
| if x % 3 == 1: |
| return (beta*x%p,a,(b+1)%n) |
| elif x % 3 == 0: |
| return (x**2%p,2*a%n,2*b%n) |
| else: |
| return (alpha*x%p,(a+1)%n,b) |
| |
| i = 1 |
| (x,a,b) = PollardRhoFunction(G[0],G[1],G[2]) |
| (x_,a_,b_) = PollardRhoFunction(x,a,b) |
| print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_)) |
| |
| while x != x_: |
| i += 1 |
| (x,a,b) = PollardRhoFunction(x,a,b) |
| (x_,a_,b_) = PollardRhoFunction(x_,a_,b_) |
| (x_,a_,b_) = PollardRhoFunction(x_,a_,b_) |
| print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_)) |
| if GCD(b_-b,n) != 1: |
| return -1 |
| else: |
| return (a-a_)*Inverse((b_-b), n)%n |
| |
| |
| if __name__ == '__main__': |
| print(PollardRhoLog((1,0,0),526483,87747,13,59480)) |