Posts Tagged ‘integer’
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 numbers have been randomly chosen.
Algorithm Input : A number N to be factorized Output : A divisor of N If x mod 2 is 0 return 2 Choose random x and c y = x g = 1 while g=1 x = f(x) y = f(f(y)) g = gcd(x-y,N) return g
Note that this algorithm may not find the factors and will return failure for composite n. In that case, use a different f(x) and try again. Note, as well, that this algorithm does not work when n is a prime number, since, in this case, d will be always 1. We choose f(x) = x*x + c. Here’s a python implementation :
def pollardRho(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
In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd’s cycle-finding algorithm with the related Brent’s cycle finding method. It is quite faster than pollard rho. Here’s a python implementation :
def brent(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