View Single Post
Old 2005-08-23, 21:14   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

749610 Posts
Thumbs up

Quote:
Originally Posted by akruppa
The squence of values (mod 4) taken by t1, t2 is

Code:
Iter.: 0 1 2 
t1:    1 2 1
t2:    1 1 1
At the third iteration, you get a difference of 0 (mod 4), thus a gcd with N discovers the divisor 4.

It is quite possible that Pollard rho discovers several small primes factors in the same iteration. If you re-run the same sequence (i.e. x=x^2+c with the same constant c), it will always rediscover the same primes in the same step, so that sequence will never split composite factors it found itself.

The probability of finding composite factors is much smaller if the primes factors are larger. Divide out very small prime factors by trial division first.

If you find a composite divisor, try splitting it with a Pollard rho routine that uses a different value for c (but not c=0, c=-1 or c=2). You could choose c randomly, or pass it as a parameter to your Pollard tho function.

Alex

Indeed. Let N = k! p, where p is a large prime and k! is also large.

I have seen Pollard Rho pull out the entire factor k! in just a few
iterations.
R.D. Silverman is offline   Reply With Quote