> From: Kris Garrett [mailto:[EMAIL PROTECTED]]
> I've noticed that with any odd number you can make the formula x^2 -
> y^2 = n where n = the odd number and x - y and x + y are
> factors of n.
> I was just wondering if one could use the graph of a hyperbola to see
> only the possible integer values of x and y.
In effect, you've just described the basis behind many factoring algorithms.
Fermat observed that if one could represent an integer as the difference of
two squares, its factorization would be at hand; he then gave an efficient
(for the 17th Century!) algorithm for finding the squares.
More recently, algorithms such Continued Fraction, Quadratic Sieve and
Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a
small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The
algorithms differ in how they construct the x and y and are *much* more
efficient than Fermat's algorithm, but the underlying idea is the same.
Paul
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
