6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What size are the integers you want to factor with this method? $\endgroup$ – naitoon Oct 7 '13 at 17:16
  • $\begingroup$ for n = 27 your code initializes with x = 6 and y = 3, which satisfy the while loop condition and give wrong result (6, 3) btw there seems to be a typo in your code initialization $\endgroup$ – user45022 Jan 17 '16 at 15:21
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

You absolutely don't have to compute most of the square roots.

You want to know whether the square root of $x^2 - n$ is an integer, that is you want to know whether $x^2 - n$ itself is a square. You don't need to know the actual square root as long as you know it is no integer.

Take d = 20,160 and create a bitmap of which integers are a square modulo 20,160 - only one in 30 is. Check whether ($x^2 - n$) modulo 20,160 is in the table. In 29 out of 30 cases the answer is "no", and $x^2 - n$ is not a square.

Also, less than one in 7 integers are squares modulo 20,387, 21,607, 17,641, or 22,231. If you add these tests then calculating a square root is needed in less than one 72,000 cases.

$\endgroup$
  • $\begingroup$ Incidentally, Fermat in his original description mentioned this idea, e.g. looking at the last few digits of $x^2 - n$ to have to find square roots only very rarely. $\endgroup$ – ShreevatsaR Apr 15 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.