View Single Post
Old 2007-07-22, 10:22   #1
mgb
 
"Michael"
Aug 2006
Usually at home

2·41 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