pollard rho for SoB?

[MJX]

the factorization method used in sob is pollard p-1 method. "Pollard rho" is another (weaker but very simple) algorithm, based on the "birthday paradox" that usually permits to find primes up to 12-13 digits. The record is 19 digits prime found for cunningham nmbers (but for composites with 300 digits on a special hardware).(http://www.cerias.purdue.edu/homes/ssw/cun/champ).

An explanation of the algorithm can be found at : http://planetmath.org/encyclopedia/PollardsRhoFactorization.html

the gimp's project can't use it since the special form of mersenne number divisors allows to sieve up to 2^62 and more...In sob project, we are sieving 15 digits numbers so my question is : can we use the pollard rho method, like the p-1, to try to factorize the composites up to 16-17 digits?

The program is by itself very easy and an implementation with gmp 4.1.2 is still done.

( 10 ' rho method (very simple sample by Hishanori Mishima for Ubasic)
20 input "n=";N
30 P=prmdiv(N):if P>1 then print P;"*";:N=N\P:goto 30
40 A=2:B=A
50 '
60 A=(A^2+1)@N
70 B=((B^2@N+1)^2+1)@N
80 G=gcd(B-A,N):if G>1 then print : print G :N=N\G:goto 80
90 goto 60 )

but there are many problems : is it realistic to hope to find 16 digits primes for 2 million digits numbers by rho in a few hours per k/n? how long does it take for a single iteration? isn't it too late *or stupid* to apply it :cry:?

best wishes.

Philippe.

[jjjjL]

I tried to write a pollard rho factorizer for proth numbers once. I used GMP in fact. It turned out not to be practical for finding factors larger than a few thousand.

Perhaps if a more suitable polynomial could be found that accounted for the unique form of proth numbers could be uncovered, this method would be useful. Standard ones like x + 1 and x^2 + 1 do not work well.

Cheers,
Louie

[MJX]

in rho for EC cryptosystem, there is no use of polynomials : I read a paper where the interval of values is cut in 3 parts. Then f(x)=x+p in the first one, f(x)=2*x in the second and x+q in the third. With well chosen p and q the fonction is cahotic and with improvements may meets rho ctiterions : recursivity, random-like, deterministic and ability to compute f(2n)... it should work with proth numbers and no squaring is involved....

hope this helps.

Best.