RhoIntFactorization.py

# Integer Factorization Algorithm
# Enes Lemal Ergin 
# 03/22/15

""" Pollard Rho is an integer factorization algorithm,
 	which is quite fast for large numbers. It is based on Floyd’s
  	cycle-finding algorithm and on the observation that two numbers 
  	x and y are congruent modulo p with probability 0.5 after 1.177\sqrt{p}
  	 numbers have been randomly chosen.
"""

# Legacy Style
def RhoIntegerFactorization(N):
        if N%2==0:
                return 2
        x = random.randint(1, N-1)
        y = x
        c = random.randint(1, N-1)
        g = 1
        while g==1:             
                x = ((x*x)%N+c)%N
                y = ((y*y)%N+c)%N
                y = ((y*y)%N+c)%N
                g = gcd(abs(x-y),N)
        return g


# Richard Brent improved Rho's Algorithm:
# This is more efficient than the Rho's Algorithm
def BrentIntegerFactorization(N):
        if N%2==0:
                return 2
        y,c,m = random.randint(1, N-1),random.randint(1, N-1),random.randint(1, N-1)
        g,r,q = 1,1,1
        while g==1:             
                x = y
                for i in range(r):
                        y = ((y*y)%N+c)%N
                k = 0
                while (k<r and g==1):
                        ys = y
                        for i in range(min(m,r-k)):
                                y = ((y*y)%N+c)%N
                                q = q*(abs(x-y))%N
                        g = gcd(q,N)
                        k = k + m
                r = r*2
        if g==N:
                while True:
                        ys = ((ys*ys)%N+c)%N
                        g = gcd(abs(x-ys),N)
                        if g>1:
                                break
         
        return g