20070722, 10:22  #1 
"Michael"
Aug 2006
Usually at home
82_{10} Posts 
Integer Factorization 2
By Fermat's factorization method we have
X^{2}  Y^{2} = pq = n. Y = (p  q) / 2 Consider the fraction p/q. Since gcd(p, q) = 1 integers x and y exist such that, py  qx = 1. If we can find x and y such that x/y ~ p/q we have, by the theory of linear congruences, (py  qx)/2 = e, a small number. We can arbitrairly choose e and find x and y. So, instead of factorizing pq we can more easily factor pqxy. Example; pq = 2003 x 4001. y = 999. but (761 x 2003)(381 x 4001) = 1524383 x 1524381 in this case y = (1524383  1524381) / 2 = 1, which is easily found by trial and error. so a multiple of n can be easier to factor. The problem is obvious, we don't know x and y. But we can produce P = p_{1}p_{2}...p_{k} where these p's are odd primes. Let x_{j}y_{j} = P. There will be many such factorizations but one will more closely approximate p/q than the others. Call this pair x_{i} and y_{i} such that x_{i}/y_{i} ~ p/q. So, we try to factor Ppq instead. We now have Y = (qx_{i}  py_{i}) / 2. The larger P is the more choices of x_{i} and y_{i} we have. We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable x_{i} and y_{i}. The only objection to this is that we must work with immense integers, but we are guarenteed of finding Y very quickly. Any comments? 
20070722, 13:23  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
This is well known. Look up Lehman's Algorithm. 

20070722, 17:27  #3 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
11×17×59 Posts 

20070722, 20:07  #4  
Jul 2007
17 Posts 
Quote:
Lehman optimized the idea as a "booster" to Fermat. His algorithm starts a Fermat factorization, but then after enough (failed) tests, it adds a multiplier to keep the effective rate as fast as possible. This reduces the factoring complexity of factoring from Fermat's O(n^(1/2)) to O(n^(1/3)). See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637646, 1974. 

20070723, 08:07  #5 
"Michael"
Aug 2006
Usually at home
2×41 Posts 
Thanks for your lucid reply fenderbender. My question was which devil is easiest to contend with; Trial and Error or Magnitude? I did not know this had been explored before. Perhaps it could be developed?
Last fiddled with by mgb on 20070723 at 08:08 
20070723, 12:55  #6  
Nov 2003
2^{2}×5×373 Posts 
Quote:
It has *already* been developed. It is a purely exponential time method and is not competitive with either ECM or indexcalculus methods. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Utility of integer factorization.  jwaltos  Other Mathematical Topics  8  20150522 12:20 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
Integer factorization with q < 2p  mgb  Math  36  20091107 15:59 
CADO workshop on integer factorization  akruppa  Factoring  14  20080918 23:52 
Integer Factorization  mgb  Math  16  20071217 10:43 