 mersenneforum.org Factoring semiprimes with restricted Rho method
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2019-07-16, 16:53 #1 mgb   "Michael" Aug 2006 Usually at home 2·41 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 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   2019-07-16, 21:04 #2 GP2   Sep 2003 13·199 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 Lucas-Lehmer don't rely on finding a factor. But are there any semi-primality tests like that?   2019-07-16, 22:04   #3
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22×3×457 Posts Quote:
 Originally Posted by GP2 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.   2019-07-17, 01:05 #4 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 43608 Posts If there are no factors less than cube-root of n, then n is either a semi-prime or prime.   2019-07-17, 08:31   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,503 Posts Quote:
 Originally Posted by a1call If there are no factors less than cube-root of n, then n is either a semi-prime or prime.
So?   2019-07-17, 13:01 #6 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 24·11·13 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 trial-by-division up to cube-root and not to square-root. These ranges would be suitable for OP purposes (I assume).   2019-07-17, 15:49 #7 chris2be8   Sep 2009 95716 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   2019-07-17, 17:23   #8
mgb

"Michael"
Aug 2006
Usually at home

1228 Posts Quote:
 Originally Posted by chris2be8 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 "interesting" 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   2019-07-17, 20:09 #9 mgb   "Michael" Aug 2006 Usually at home 2·41 Posts p 34094494829 q 15154262241479 n 516676915629415714812091 in 53065360 iterations   2019-07-17, 20:14   #10
CRGreathouse

Aug 2006

5,987 Posts Quote:
 Originally Posted by chris2be8 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)?
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.   2019-07-17, 22:05 #11 jwaltos   11011100011002 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 11 2018-02-28 11:29 Alberico Lepore Alberico Lepore 43 2017-06-10 15:42 3.14159 Factoring 233 2011-05-15 18:50 3.14159 Miscellaneous Math 29 2010-05-31 23:21 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

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔