20060204, 14:18  #1 
Jun 2005
2·7^{2} 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 (PxCx)< 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 (PxCx) < 100 Sqrt[Px] Regards Anton 
20060204, 17:53  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·3,529 Posts 
Quote:
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 

20060205, 00:43  #3  
Nov 2005
48_{10} Posts 
Quote:
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 20060205 at 00:45 

20060205, 06:30  #4 
Jun 2005
2·7^{2} 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 , x1k) 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= x1k 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 x1k =...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? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring n via factors of n1 or n+1  a1call  Miscellaneous Math  63  20180306 09:39 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
option for finding multiple factors during trial factoring  tha  Software  24  20140610 23:31 
What's the point of factoring known composites?  ixfd64  PrimeNet  4  20110221 11:51 
Types of work to request from server : Add P1 Factoring  MoZ  Software  2  20040206 20:24 