| 0,0 → 1,88 |
|---|
| |
| def PollardPM1(N,B): |
| '''Implementation of the Pollard p-1 algorithm for factoring primes''' |
| a = 2; |
| for i in range(2,B): |
| a = a**i % N |
| d = GCD(a-1,N) |
| if 1 < d < N: |
| return d |
| else: |
| return -1; |
| |
| def PollardRho(N,x_1): |
| '''Implementation of the Pollard Rho algorithm for factoring primes''' |
| x = x_1 |
| y = PollardRhoHelper(x) % N |
| g = GCD(abs(x-y),N) |
| iterations = 0; |
| while g == 1: |
| iterations += 1 |
| x = PollardRhoHelper(x) % N |
| y = PollardRhoHelper(y) % N |
| y = PollardRhoHelper(y) % N |
| g = GCD(abs(x-y),N) |
| print("Iterations: %d\n" % (iterations)) |
| if g == N: |
| return -1 |
| else: |
| return g |
| |
| def PollardRhoHelper(x): |
| return x**2 + 1 |
| |
| 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 = int(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 = int(a/b) |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| |
| def GCD(q,N): |
| '''Returns the multiplicative inverse of a and b''' |
| ret = Extended_Euclidian(q,N) |
| return ret[0] |
| |
| 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 |
| |
| if __name__ == '__main__': |
| prime1 = 112426043 |
| prime2 = 262063 |
| prime3 = 9420457 |
| |
| for i in range(100): |
| p = PollardPM1(prime1,i) |
| if p != -1: |
| print("Prime found with B = %d with value %d\n" % (i,p)) |
| break |
| |
| p = PollardRho(prime2,1) |
| print("A prime factor of %d is %d\n" % (prime2,p)) |
| |
| p = PollardRho(prime3,1) |
| print("A prime factor of %d is %d\n" % (prime3,p)) |