mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-07-16, 16:53   #1
mgb
 
"Michael"
Aug 2006
Usually at home

2·41 Posts
Default 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 z2 (defined below) increasing the chances of finding a cancellation. It also uses a multiplier to increase the roots of z2 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
m2 = z2 mod p so
Let r = n - m2 = -z2 mod p
m2 = z2 mod p, has two roots, z and p - z

So here we have two different ways of writing z2 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 = m2
Let Q = n - m2

The loop is as follows-
R = R2 mod n
R = R2 mod n (square twice mod n to get ahead of Q)
Q = Q2 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 z2 and -z2 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 m2 = (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 2019-07-16 at 16:56
mgb is offline   Reply With Quote
Old 2019-07-16, 21:04   #2
GP2
 
GP2's Avatar
 
Sep 2003

13·199 Posts
Default

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 Lucas-Lehmer don't rely on finding a factor. But are there any semi-primality tests like that?
GP2 is offline   Reply With Quote
Old 2019-07-16, 22:04   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×3×457 Posts
Default

Quote:
Originally Posted by GP2 View Post
This is only tangentially related, but:

How do you know in advance that a number is a semiprime?
Well, all RSA numbers, for one; common crypto methods use semiprimes.

If you ECM-pretest 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.
VBCurtis is online now   Reply With Quote
Old 2019-07-17, 01:05   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

43608 Posts
Default

If there are no factors less than cube-root of n, then n is either a semi-prime or prime.
a1call is offline   Reply With Quote
Old 2019-07-17, 08:31   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,503 Posts
Default

Quote:
Originally Posted by a1call View Post
If there are no factors less than cube-root of n, then n is either a semi-prime or prime.
So?
xilman is offline   Reply With Quote
Old 2019-07-17, 13:01   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

24·11·13 Posts
Default

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 trial-by-division up to cube-root and not to square-root. These ranges would be suitable for OP purposes (I assume).
a1call is offline   Reply With Quote
Old 2019-07-17, 15:49   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

95716 Posts
Default

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 &quot;interesting&quot; 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
chris2be8 is offline   Reply With Quote
Old 2019-07-17, 17:23   #8
mgb
 
"Michael"
Aug 2006
Usually at home

1228 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
What happens if you try it on a number that's the product of 3 or more primes? Does it still find one?
Faster for 3 primes. Generally speaking, semiprimes are hardest.

Quote:
How does average run time vary with the size of the prime factors?
So far I only tested up to 12 digits or so but I'll try bigger ones soon.

Quote:
How long does it take for &quot;interesting&quot; numbers (too large for GNFS to be practical, ie over about 300 digits)?
Didn't go near them yet but I'll get back to you.

Quote:
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?
Run time seems to depend on the factorization of p-1 or q-1. Safe primes are hardest to find but it finds them.

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 2019-07-17 at 18:12
mgb is offline   Reply With Quote
Old 2019-07-17, 20:09   #9
mgb
 
"Michael"
Aug 2006
Usually at home

2·41 Posts
Default

p 34094494829 q 15154262241479 n 516676915629415714812091 in 53065360 iterations
mgb is offline   Reply With Quote
Old 2019-07-17, 20:14   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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 &quot;interesting&quot; numbers (too large for GNFS to be practical, ie over about 300 digits)?
It's a rho method, so the size of interest should be somewhere in the range of 10-30 digits. 300 digits will run very poorly.

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 general-purpose factorization algorithms.
CRGreathouse is offline   Reply With Quote
Old 2019-07-17, 22:05   #11
jwaltos
 

11011100011002 Posts
Default

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?
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A stupid factoring method JM Montolio A Miscellaneous Math 11 2018-02-28 11:29
Semiprimes factoring. Is deterministic? What is computational complexity? Alberico Lepore Alberico Lepore 43 2017-06-10 15:42
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
A (very) weak factoring method. 3.14159 Miscellaneous Math 29 2010-05-31 23:21
Factoring semiprimes robert44444uk Math 34 2007-07-19 17:23

All times are UTC. The time now is 05:37.


Mon Oct 3 05:37:22 UTC 2022 up 46 days, 3:05, 1 user, load averages: 1.01, 1.02, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”