20190716, 16:53  #1 
"Michael"
Aug 2006
Usually at home
52_{16} Posts 
Factoring semiprimes with restricted Rho method
This algorithm uses a very simplified version of Pollard's Rho method on a well defined set of residues. The idea is that if the Rho function is restricted it can only produce multiples of z^{2} (defined below) increasing the chances of finding a cancellation. It also uses a multiplier to increase the roots of z^{2} mod p where p is a factor of n, the number to be factored.
Let p and q be primes, p < q and pq = n. Let m = [sqrt(n)] Let z = m mod p m^{2} = z^{2} mod p so Let r = n  m^{2} = z^{2} mod p m^{2} = z^{2} mod p, has two roots, z and p  z So here we have two different ways of writing z^{2} and the idea is to use Pollards's Rho method to separate out a multiple of p from them. Here is the Rho method for this system. Let R = m^{2} Let Q = n  m^{2} The loop is as follows R = R^{2} mod n R = R^{2} mod n (square twice mod n to get ahead of Q) Q = Q^{2} mod n X = R  Q test gcd(X, n) It is essential to keep this Rho method as simple as possible because adding random seeds will disrupt the multiples of z^{2} and z^{2} mod p As it stands this algorithm can have good results but seems to be much better when a multiplier is used so that a multiple of n is being factored. The effect of multiplying seems to effectively increase the roots of m^{2} = (cp + z)^{2} where cp < m < (c + 1)p. This increases to roots to z, p + z, 2p + z, 3p + z etc Results: p 3228341 q 4941967 n 510539349975904 factored at 140 iterations p 2001049 q 5225501 n 334607473617568 factored at 644 iterations p 2462041 q 5294981 n 1316682491938321 factored at 1464 iterations p 2082593 q 4596979 n 306356361169504 factored at 645 iterations p 3256831 q 4997917 n 1644014473123727 factored at 450 iterations p 3210643 q 4629809 n 1501331049575887 factored at 88298 iterations p 2822923 q 4242421 n 1209578809474883 factored at 36 iterations The algorithm can be very fast but uneven so I'll let you make your own assessment if you like to try it. Here is the program in Pari (It is using multiplier = 32 but this can be changed to whatever you like) RhoN() = { local(p, q, n, m, r, Q, R, X, i); p = randomprime([2000000, 4000000]); q = randomprime([4000000, 6000000]); n = p*q*32; print(" p " p " q " q " n " n); m = floor(sqrt(n)); r = n  m^2; R = r; Q = n  r; print(" R, Q " R ", " Q); for(i = 1, r, R = R^2%n; R = R^2%n; Q = Q^2%n; X = abs(R  Q); if(X%p == 0, print(" X = " X " at (p) " i); break; ); if(X%q == 0, print(" X = " X " at (q) " i); break; ); ); } RhoN(); Last fiddled with by mgb on 20190716 at 16:56 
20190716, 21:04  #2 
Sep 2003
5031_{8} Posts 
This is only tangentially related, but:
How do you know in advance that a number is a semiprime, unless you have already found a factor somehow and then the cofactor passed a PRP test, in which case any factoring algorithm is moot. Primality tests like LucasLehmer don't rely on finding a factor. But are there any semiprimality tests like that? 
20190716, 22:04  #3  
"Curtis"
Feb 2005
Riverside, CA
3^{3}·191 Posts 
Quote:
If you ECMpretest to around 33% of input size, you can conclude (with substantial uncertainty) that the input is a semiprime. This is on the order of double or triple the optimal amount of pretesting before GNFS, but when GNFS was slower it wasn't unreasonable to pretest to digits/3, and many people did a bit more to "be sure" the input wouldn't split into 3 primes. 

20190717, 01:05  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
4225_{8} Posts 
If there are no factors less than cuberoot of n, then n is either a semiprime or prime.

20190717, 08:31  #5 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{2}·11^{2}·23 Posts 

20190717, 13:01  #6 
"Rashid Naimi"
Oct 2015
Remote to Here/There
4225_{8} Posts 
It was a reply to post number 2, and I actually did lose sleep for not saying less than or equal to.
There are number ranges for which it is practical to trialbydivision up to cuberoot and not to squareroot. These ranges would be suitable for OP purposes (I assume). 
20190717, 15:49  #7 
Sep 2009
100010101110_{2} Posts 
What happens if you try it on a number that's the product of 3 or more primes? Does it still find one?
How does average run time vary with the size of the prime factors? How long does it take for "interesting" numbers (too large for GNFS to be practical, ie over about 300 digits)? How does average run time vary if the prime factors are different sizes? Does average run time depend on the size of the smallest factor? Chris 
20190717, 17:23  #8  
"Michael"
Aug 2006
Usually at home
2×41 Posts 
Quote:
Quote:
Quote:
Quote:
Has anybody tested this program? _________________________ Just factored p 15489151 q 31266397 n 12107248608973675 in 780 iterations. p 961748969 q 981863147 n 23607646733158636075 in 240856 iterations. (I'm using multiplier 25 to factor 25n) Last fiddled with by mgb on 20190717 at 18:12 

20190717, 20:09  #9 
"Michael"
Aug 2006
Usually at home
122_{8} Posts 
p 34094494829 q 15154262241479 n 516676915629415714812091 in 53065360 iterations

20190717, 20:14  #10  
Aug 2006
175B_{16} Posts 
Quote:
Generally speaking they don't work well when there are small prime factors; it's ok if there are 3 prime factors as long as the smallest is decently large. That's why rho (or more usually SQUFOF) is done after the initial trial division in the generalpurpose factorization algorithms. 

20190717, 22:05  #11 
Apr 2012
Gracie on lookout.
419 Posts 
I don't know if this is possible within the framework of your program but have you tried to "artificially" create a solution path to any of the factored RSA challenge numbers? At the very least these results will provide an optimal or ideal benchmark. Basically, my question is have to tried to contrive an optimal path to known and factored RSA and Mersenne numbers?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A stupid factoring method  JM Montolio A  Miscellaneous Math  11  20180228 11:29 
Semiprimes factoring. Is deterministic? What is computational complexity?  Alberico Lepore  Alberico Lepore  43  20170610 15:42 
Another factoring method rides the bus  3.14159  Factoring  233  20110515 18:50 
A (very) weak factoring method.  3.14159  Miscellaneous Math  29  20100531 23:21 
Factoring semiprimes  robert44444uk  Math  34  20070719 17:23 