mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-07-22, 10:22   #1
mgb
 
"Michael"
Aug 2006
Usually at home

24×5 Posts
Default 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?
mgb is offline   Reply With Quote
Old 2007-07-22, 13:23   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by mgb View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-07-22, 17:27   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·1,733 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is well known.
It was known by Fermat.

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


Paul
xilman is online now   Reply With Quote
Old 2007-07-22, 20:07   #4
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default

Quote:
Originally Posted by mgb View Post

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.
fenderbender is offline   Reply With Quote
Old 2007-07-23, 08:07   #5
mgb
 
"Michael"
Aug 2006
Usually at home

8010 Posts
Default

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
mgb is offline   Reply With Quote
Old 2007-07-23, 12:55   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by mgb View Post
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?
Perhaps you might do some reading about the subject???

It has *already* been developed. It is a purely exponential time
method and is not competitive with either ECM or index-calculus
methods.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Utility of integer factorization. jwaltos Other Mathematical Topics 8 2015-05-22 12:20
Integer factorization? bearnol2 Information & Answers 7 2010-12-09 02:50
Integer factorization with q < 2p mgb Math 36 2009-11-07 15:59
CADO workshop on integer factorization akruppa Factoring 14 2008-09-18 23:52
Integer Factorization mgb Math 16 2007-12-17 10:43

All times are UTC. The time now is 18:31.

Fri Dec 4 18:31:30 UTC 2020 up 1 day, 14:42, 0 users, load averages: 1.37, 1.52, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.