## Pollard Rho Brent Integer Factorization

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.

AlgorithmInput : 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

-fR0DDY

Found your note about Pollard’s method. It always sounded intimidating…and then I read about it; found your page; it all doesn’t seem so bad.

sympy, a CAS in pure python, has this method as part of it’s number theory module. You might be interested in checking it out.

C SmithOctober 12, 2010 at 1:02 AM

Thanks, very Useful.

Though I need analyse these codes… but the more Description, the more useful… 😀

Tnx

AfshinFebruary 2, 2011 at 2:58 AM

Great blog bro.

Ahmet Alp BalkanMarch 31, 2011 at 4:47 PM

how do we get all the distinct factors of an integer by this method?

Thanks.

pranayAugust 1, 2011 at 11:27 PM

This is the best idea about integer factorization, written here is to let more people know and participate.

A New Way of the integer factorization

1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known Large integer.

True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).

How do I know "k" and "y"?

"P" is a factor of "N",GCD(k,N)=P.

Two Special Presentation:

N=5287

1+2+3+…k=Ny

Using the dichotomy

1+2+3+…k=Nrm

"r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)

"m" is Square

(K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)

(K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)

(K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)

(K^2+k)/(2*256)=5287*1.75 k=2176(OK)

K=2176,y=448

GCD(2176,5287)=17

5287=17*311

N=13717421

1+2+3+…+k=13717421y

K=4689099,y=801450

GCD(4689099,13717421)=3803

13717421=3803*3607

The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!

True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).

More details of the process in my G+ and BLOG.

My G+ :https://plus.google.com/u/0/108286853661218386235/posts

My BLOG:http://hi.baidu.com/s_wanfu/item/00cd4d3c5a2fd089f5e4ad0a

Email:wanfu.sun@gmail.com

s-987618November 22, 2012 at 7:23 PM

hey thanks a lot for this, I appreciate it. I looked through a couple of different pages and this is the first one that really made sense.

alexr1090May 1, 2013 at 10:13 PM

Glad I could help.

fR0DDYMay 1, 2013 at 10:45 PM

Hey! This is a great blog. I went ahead and took your code and was trying some stuff more out on it (More euler problems actually) and i somehow ended up with a weird case. Sometimes, just sometimes when im giving in 9 as the input, i get a 9 as the output. Essentially it should be 3 right?

Is this a problem with my understanding? Any insight would be helpful.

Cheers & great work!

shrayasAugust 30, 2013 at 11:03 PM

Hi!

In your code you calculate q with q = q*(abs(x-y))%N. Since you using mod N then q must be between 0 and N-1 (but could also be N-1 or 0). Then you use determine g with g = gcd(q,N) and g cant be N since q is smaller than N. So why are you checking if g=N in row 19?

JesperNovember 13, 2013 at 4:56 PM

Although q is always less than N, that does not mean that gcd(q, N) can not be equal to N. Consider the case when q = 0. In such case, g = gcd(0, N) = N.

mdimrulhassanJanuary 26, 2016 at 8:51 PM

Thanks! Note that to get gcd, you also need to add “from fractions import gcd”

nealmcbDecember 15, 2013 at 8:44 PM