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?
