MJX
02-08-2004, 08:59 AM
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.
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.