 mersenneforum.org > Math Integer Factorization 2
 Register FAQ Search Today's Posts Mark Forums Read 2007-07-22, 10:22 #1 mgb   "Michael" Aug 2006 Usually at home 24·5 Posts Integer Factorization 2 By Fermat's factorization method we have X2 - Y2 = 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 = p1p2...pk where these p's are odd primes. Let xjyj = P. There will be many such factorizations but one will more closely approximate p/q than the others. Call this pair xi and yi such that xi/yi ~ p/q. So, we try to factor Ppq instead. We now have Y = (qxi - pyi) / 2. The larger P is the more choices of xi and yi we have. We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable xi and yi. The only objection to this is that we must work with immense integers, but we are guarenteed of finding Y very quickly. Any comments?   2007-07-22, 13:23   #2
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by mgb By Fermat's factorization method we have X2 - Y2 = 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 = p1p2...pk where these p's are odd primes. Let xjyj = P. There will be many such factorizations but one will more closely approximate p/q than the others. Call this pair xi and yi such that xi/yi ~ p/q. So, we try to factor Ppq instead. We now have Y = (qxi - pyi) / 2. The larger P is the more choices of xi and yi we have. We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable xi and yi. The only objection to this is that we must work with immense integers, but we are guarenteed of finding Y very quickly. Any comments?
Once more, someone reinvents the wheel.

This is well known. Look up Lehman's Algorithm.   2007-07-22, 17:27   #3
xilman
Bamboozled!

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

33×389 Posts Quote:
 Originally Posted by R.D. Silverman This is well known.
It was known by Fermat.

Exercise: Re-discover which which N was factored by Fermat himself by factoring 8N.

Paul   2007-07-22, 20:07   #4
fenderbender

Jul 2007

1710 Posts Quote:
 Originally Posted by mgb The larger P is the more choices of xi and yi we have. We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable xi and yi. The only objection to this is that we must work with immense integers, but we are guarenteed of finding Y very quickly.
The flaw is in these last assumptions. Yes, the large multiplier starts giving you multiple different "splits" and the big product can be factored into a closer-to-a-square set of factors. But the bonus of having the multiple split options is offset much more rapidly by the larger value to factor, so the search will still end up being slower.

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:637-646, 1974.   2007-07-23, 08:07 #5 mgb   "Michael" Aug 2006 Usually at home 24·5 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 2007-07-23 at 08:08   2007-07-23, 12:55   #6
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by mgb 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?

It has *already* been developed. It is a purely exponential time
method and is not competitive with either ECM or index-calculus
methods.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Other Mathematical Topics 8 2015-05-22 12:20 bearnol2 Information & Answers 7 2010-12-09 02:50 mgb Math 36 2009-11-07 15:59 akruppa Factoring 14 2008-09-18 23:52 mgb Math 16 2007-12-17 10:43

All times are UTC. The time now is 20:53.

Tue Jan 19 20:53:53 UTC 2021 up 47 days, 17:05, 0 users, load averages: 1.95, 1.95, 1.97