Factoring integers—Fermat and Kraitchik

Fermat

Some integers with no obvious small divisor, such as for example $8051$, are nonetheless easily factored on paper. One need only notice that
\[ 8051 = 8100-49 = 90^2 – 7^2, \]
and use the well-known identity $a^2-b^2 = (a+b)(a-b)$ to find that $8051 = 83\times 97$.

This method of factoring an integer by writing it as a difference of two squares is generally attributed to Fermat. However, although it is always possible to write an odd composite as a difference of two squares (as $ab = \left(\frac{a+b}{2}\right)^2-\left(\frac{a-b}{2}\right)^2$), this method by itself makes for a lousy factoring algorithm. We can implement it in Sage like this:

def fermat(n):
    x = ceil(sqrt(n))
    while not is_square(x^2-n):
        x = x+1
    y = sqrt(x^2-n)
    return (x+y, x-y)

but this algorithm will work only if $n$ has a divisor near its square root, which most numbers do not. On the other hand, the naive factoring algorithm by trial division will work on numbers which have one relatively small factor, which most numers do, so this algorithm is most often even worse than trial division. However, the most powerful factoring algorithms today are refinements of this simple idea.

Kraitchik

The first one was popularised by Kraitchik in the 1920s (although the idea was known at least since Gauss). Instead of looking for integers $x$ and $y$ such that $x^2-y^2$ equals $n$, we ask only that $x^2-y^2$ be a multiple of $n$. Thus, $(x+y)(x-y)$ will be a multiple of $n$, and if it also happens that neither of $x+y$ and $x-y$ is a multiple of $n$, it means that the factors of $n$ are “split” between $x+y$ and $x-y$, and finally that $\gcd(n, x\pm y)$ will be non-trivial divisors of $n$. This gives for example the following algorithm:

def kraitchik(n):
    x = ceil(sqrt(n))
    while True:
        k = 1
        while x^2 - k*n >= 0:
            if is_square(x^2-k*n):
                y = sqrt(x^2-k*n)
                if (x+y) % n != 0 and (x-y) % n != 0:
                    a = gcd(x+y, n)
                    b = gcd(x-y, n)
                    return (a, b, n//(a*b))
            k = k+1
        x = x+1

which, albeit an improvement over the preceeding one, is still not at all practical.

In fact, Kraitchik does something else. Instead of trying $x^2-kn$ for various values of $x$ and $k$ until a square is found, he keeps the value $x^2-n$ of the previous Fermat method. However, instead of trying individual values to see if one of them is a square, he keeps the previous values and tries to find a product of such values which is a square. Say we have values $x_1, x_2, \dots, x_k$ such that $\prod \left(x_i^2 – n\right) = y^2$. Since obviously $x_i^2-n \equiv x_i^2 \pmod n$, we obtain that
\[ y^2 \equiv \prod \left(x_i^2-n\right) \equiv \prod x_i^2 \equiv \left(\prod x_i\right)^2 \pmod n, \]
and voilà our congruence of squares.

The problem, now, is how to find our values $x_1,\dots,x_k$ which produce a square. Kraitchik used only trial and error, which is obviously not very suitable for an algorithm. A systematic method for this was not introduced until the 1970s. I will cover it in a coming post.

Leave a Reply

Your email address will not be published. Required fields are marked *