Thread: Integer Factorization 2 View Single Post
 2007-07-22, 10:22 #1 mgb   "Michael" Aug 2006 Usually at home 2·41 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?