mersenneforum.org Factoring of composites with near factors - request for data
 Register FAQ Search Today's Posts Mark Forums Read

 2006-02-04, 14:18 #1 AntonVrba     Jun 2005 2×72 Posts Factoring of composites with near factors - request for data I think, I can factor extremely fast, a composite number Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px] regardless of the size of Px (Px prime, Cx prime or composite) I would appreciate some test data for Q = 300, 600 and 1000 decimal digits but please keep restraint (Px-Cx) < 100 Sqrt[Px] Regards Anton
2006-02-04, 17:53   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

11,369 Posts

Quote:
 Originally Posted by AntonVrba I think, I can factor extremely fast, a composite number Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px] regardless of the size of Px (Px prime, Cx prime or composite) I would appreciate some test data for Q = 300, 600 and 1000 decimal digits but please keep restraint (Px-Cx) < 100 Sqrt[Px] Regards Anton
Three observations:

First, you can easily produce your own test data. There's no need for you to get it from elsewhere.

Second, it sounds very much like you have reinvented Fermat's factoring algorithm.

Third, only an exceedingly small fraction of numbers with 300 digits (and even smaller fractions of larger numbers) meet your criteria.

Post your algorithm and lets take a look at it.

Paul

2006-02-05, 00:43   #3
John Renze

Nov 2005

24×3 Posts

Quote:
 Originally Posted by AntonVrba I think, I can factor extremely fast, a composite number Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px] regardless of the size of Px (Px prime, Cx prime or composite)
Lenstra's algorithm (C&P Algorithm 4.2.11) can do this with sqrt(Px) replaced by (Px)^2/3.

Edit: Never mind. Lenstra's algorithm is for low bits known, not high bits known. BUT, Coppersmith's LLL techniques work for the case Anton is talking about, all the way up to (Px)^3/4.

Last fiddled with by John Renze on 2006-02-05 at 00:45

 2006-02-05, 06:30 #4 AntonVrba     Jun 2005 2×72 Posts The Algorithm After posting I noticed my result is not that spectacular, and I have been asked to share my algorithm, well here goes: For Q= Px Cx (Px and Cx being near ) using notation [ ] meaning floor function or integerpart Let b = [ Sqrt(Q) ] x0 = Mod(Q , b) x1 = [Q / b] k= [Sqrt( i*b - x0) - i/2]+1 then Px = GCD(x0 + k * b , x1-k) and "i" being an integer quantity! even more baffeling: Let p1 be a prime Let p2 be the nearest prime to p1+[s * sqrt(p1)] Q= p1 p2 then b = [ Sqrt(Q) ] i=[(s^2)/4] or i=[s^2/4]+1 k= [Sqrt( i*b - x0) - i/2]+1 p1= x1-k Above holds for s < p1^1/6 (sixth root) Trivial example: q1= 3 10^12 + 13 = 3000000000013 s=[q1^1/6]=120 q2= q1+[s sqrt(q1)]+40 = 3000207846149 (+40 for next prime) Q=9000623538486002701999937 b = 3000103921281 x0 = 370057318976 x1 = 3000103921281 i = (120^2)/4=3600 k = [Sqrt( i*b - x0) - i/2]+1 = 103921268 x1-k =...281 - ...268 = 3000000000013 = p1 Now my thinking is: if k= [Sqrt( i*b - x0) - i/2]+1 is an approximation of a higher order polynomial then it should be possible that the range can be extended and the iterration to find the factors of Q is done over "i" Any comments?

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 63 2018-03-06 09:39 UberNumberGeek Factoring 51 2017-02-13 20:30 tha Software 24 2014-06-10 23:31 ixfd64 PrimeNet 4 2011-02-21 11:51 MoZ Software 2 2004-02-06 20:24

All times are UTC. The time now is 06:28.

Mon Jun 27 06:28:29 UTC 2022 up 74 days, 4:29, 1 user, load averages: 0.98, 1.04, 1.01