integer factoring using Fermat's method Reading an article on integer factorization I implemented the following -  rather inefficient - factorization method:  


  Every odd
  composite can be factored as a difference of
  squares: $$ ab = \left[\tfrac{1}{2}(a+b)\right]^2 -
 \left[\tfrac{1}{2}(a-b)\right]^2$$ 
  We can look at values of $f(x) = x^2 - n$ until we find a perfect square and factor.


Here's my implementation in Python.



def fermat(n):
    x = int(np.sqrt(n))+1
    y = int(np.sqrt(abs(y*y - n)))

    while( n - x*x + y*y != 0):
        x += 1
        y = int(np.sqrt(abs(x*x - n)))

    return x, y


How expensive are the square root calculations here?  Are they necessary?
In order to check I have a perfect square, I compute $\lfloor \sqrt{x^2-n}\rfloor$ many times.
Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing floating-point square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and moreover the range of floating-point numbers is limited. Use a bignum package instead.