Factoring integers—Factor bases

We are now facing the following problem: given an integer $n$ which we wish to factor, find integers $x_1,\dots,x_k$ such that $\prod \left(x_i^2-n\right)$ is a square. We mentioned in the previous post that Kraitchik basically used trial and error to find such values, but still he did not try completely random values.

Say we now wish to factor $n = 2587$. The values of $x^2-n$ for various values of $x$ are as follows:
\[ \begin{array}{c | l}
x & x^2-n \\
\hline
51 & 14 \\
52 & 117 \\
53 & 222 \\
61 & 1134 \\
62 & 1257 \\
63 & 1382
\end{array} \]
Kraitchik noticed that some of those numbers factor very easily even using trial division: we have $14 = 2\times 7$ of course, but also $1134 = 2\times 3^4\times 7$. This at once gives us the desired square:
\[ \begin{align*}
14 \times 1134
&= 2\times 7\times 2\times 3^4\times 7 \\
&= 2^2\times 3^4\times 7^2 \\
&= \left(2\times 3^2\times 7\right)^2 \\
&= 126^2,
\end{align*} \]
and thus the congruence $(51\times 61)^2 \equiv 126^2 \pmod n$. We are lucky: neither of $51\times 61 \pm 126$ is a multiple of $n$, and we obtain the non-trivial divisors $\gcd(51\times 61+126, n) = 13$ and $\gcd(51\times 61-126, n) = 199$ of $n$.

Factor bases

The above method is still very much imprecise. It was formalised by Brillhart and Morrison in 1975 in an article in which they also presented a factorisation of the seventh Fermat number $F_7 = 2^{2^7} – 1$ which they had obtained using their new method. Somewhat surprisingly, it is basically just linear algebra.

What we did above was find values $x^2-n$ which had only “small” prime factors. The first thing we need to do is to define “small”, which we do in a straghtforward way: we say that a number has only “small” prime factors if all its prime factors are smaller than a given upper bound $B$ (such numbers are called “$B$-smooth”). We will see later that choosing a suitable $B$ is not completely straightforward, but for now we will be content with $B=7$. So we do as above until we find numbers whose only prime factors are $2$, $3$, $5$, or $7$ (the set $\{2,3,5,7\}$ is then what Brillhart and Morrison call the factor base). Let us try now with $n = 3439$, we find
\[ \begin{array}{c | l}
x & x^2-n \\
\hline
59 & 42 = 2\times 3\times 7 \\
62 & 405 = 3^4\times 5 \\
67 & 1050 = 2\times 3\times 5^2\times 7 \\
73 & 1890 = 2\times 3^3\times 5\times 7 \\
143 & 17010 = 2\times 3^5\times 5\times 7
\end{array} \]
We define for each of those values its exponent vector in a natural way:
\[ \begin{align*}
v(42) &= (1, 1, 0, 1), \\
v(405) &= (0, 4, 1, 0), \\
v(1050) &= (1, 1, 2, 1), \\
v(1890) &= (1, 3, 1, 1), \\
v(17010) &= (1, 5, 1, 1),
\end{align*} \]
and we note that the exponent vector of the product of two values will be the sum of their exponent vectors. We want a product which is a square, and it is clear that a number is a square if and only if all the entries of its exponent vector are even. Thus we are only interested in the parity of the entries of exponent vectors, and not in their precise value, and it seems a good idea to reduce them modulo $2$ to discard the superfluous information. The vectors become
\[ \begin{align*}
v(42) &= (1, 1, 0, 1), \\
v(405) &= (0, 0, 1, 0), \\
v(1050) &= (1, 1, 0, 1), \\
v(1890) &= (1, 1, 1, 1), \\
v(17010) &= (1, 1, 1, 1),
\end{align*} \]
and, seeing them now as vectors with coordinates in $\mathbf{F}_2$, we wish to obtain a set of vectors whose sum is the zero vector. In other words, which are linearly dependent.

Here we are lucky because we have plenty of choices, including two very obvious pairs of equal vectors. We can for example use the congruence
\[ \begin{align*}
3953^2
&\equiv (59\times 67)^2 \\
&\equiv 42\times 1050 \\
&\equiv 2\times 3\times 7\times 2\times 3\times 5^2\times 7 \\
&\equiv 2^2\times 3^2\times 5^2\times 7^2 \\
&\equiv \left(2\times 3\times 5\times 7\right)^2 \\
&\equiv 210^2\pmod n,
\end{align*} \]
and since none of $3953\pm 210$ is a multiple of $n$, we obtain the non-trivial divisors $\gcd(3953-210, n) = 19$ and $\gcd(3953+210, n) = 181$.

The strength of this method, however, comes from its systematicity. If the factor base is much larger than in our example, it might be difficult to spot sets of linearly dependent vectors, and in any case, we cannot just tell a computer to look and find them. However, if we let $d$ be the number of primes in our factor base, our exponent vectors will be vectors of the vector space $\mathbf{F}_2^d$, and since this vector space has dimension $d$, linear algebra tells us that we need only find at most $d+1$ vectors in order to be certain to find a linear dependence.

Also, remember that even if we find a set of linearly dependent vectors, which gives a congruence $x^2\equiv y^2\pmod n$, the game is not necessarily over. We also require that $x\not\equiv \pm y\pmod n$, and so we might need to find several congruences (and thus, several set of linearly dependent vectors) until we find a satisfactory one. Linear algebra helps us here also: if we have gathered a large number of vectors, we have good algorithms from linear algebra which will help us find subsets of linearly dependent vectors.

How to choose $B$?

This is not easy. If we choose it small, $B$-smooth numbers will be very rare, and we will thus need to try a large amount of values until we find enough numbers with good exponent vectors. On the other hand, if we choose it large, $B$-smooth numbers will be more difficult to identify (since we will need to factor them up to a larger bound), and we will also need more of them (since we need at least as many as there are primes in our factor base, plus one).

Rigorously finding an ideal value of $B$ involves complicated analytic number theory. Two important ideas are that it is better to choose it too large than too small, and also that the ideal value is about $\exp\left(\frac{1}{2}\sqrt{\log n \log\log n}\right)$.

Negative values

So far, we have only computed $x^2-n$ for $x > \sqrt{n}$, so we always had $x^2-n > 0$. There seems to be no reason to restrict ourselves to positive values. Indeed, continuing with the example $n = 3439$, we find
\[ \begin{array}{c | l}
x & x^2-n \\
\hline
58 & -75 = (-1)\times 3\times 5^2 \\
53 & -630 = (-1)\times 2\times 3^2\times 5\times 7 \\
52 & -735 = (-1)\times 3\times 5\times 7^2 \\
46 & -1323 = (-1)\times 3^3\times 7^2
\end{array} \]
which gives
\[ \begin{align*}
2668^2
&\equiv (58\times 46)^2 \\
&\equiv (-75)\times (-1323) \\
&\equiv (-1)\times 3\times 5^2\times (-1)\times 3^3\times 7^2 \\
&\equiv (-1)^2\times 3^4\times 5^2\times 7^2 \\
&\equiv \left(3^2\times 5\times 7\right)^2 \\
&\equiv 315^2\pmod n,
\end{align*} \]
which gives the non-trivial divisors $\gcd(2668+315, n) = 19$ and $\gcd(2668-315, n) = 181$.

So using negative values seems to work just fine, and actually it has an advantage. As $x$ goes farther away from $\sqrt{n}$, $x^2-n$ goes farther away from $0$, and obviously, the larger an integer is in absolute value, the smaller the probability that it will be smooth. If we use only positive values of $x^2-n$, after a while it will be so large that it will almost never be smooth. On the other hand, if we also use negative values, we will have twice as much values of $x^2-n$ in the same range of absolute value, and thus twice as much chance to find smooth ones.

For this benefit, using negative values has negligible cost: we just add the “prime” $-1$ to our factor base. This does not change the idea of the method, because since a square is always positive, we will also need the exponent of $-1$ to be even, just like that of the other primes. The cost is that since we have one more element in our factor base, we will need to find one more vector if we want to be certain to find a linear dependence. Since in exchange we will obtain twice as many vectors to choose from, this is quite a bargain.

Okay, fine, but show me the code!

This post is getting long, so we’ll get coding in the next one. We will see Dixon’s algorithm, which is the straightforward implementation of the ideas we have discussed so far, and was introduced by Dixon in 1981. This seems odd, because we have said that Brillhart and Morrison introduced the factor base method in 1975. In fact, they originally applied their method to a different algorithm, which used continued fractions instead of the polynomial $x^2-n$, and was the leading algorithm at the time. Since continued fractions are not very pretty and the continued fractions algorithm is no longer used today, we do not discuss it here.

7 thoughts on “Factoring integers—Factor bases

  1. Ada Lovelace

    Hi!
    Very nice article, thanks for sharing.
    I would like to read something more about choosing the cardinality of B, do you still remember the source supporting your statement about its ideal size?

    Reply
  2. Windy

    Hello Firas.

    Could you please advise me a good introductory book to number theory? There are three that have a good reputation on the net: Hardy & Wright, Rosen and Silverman. What are in your opinion the strenghts of those? Please feel free to bring up any one you think is better.

    Thank you.

    Reply
    1. Firas Post author

      Hardy and Wright is a huge classic, but it is big and quite terse, so can be a bit intimidating. Silverman is excellent, but quite pricey. I don’t know Rosen.

      If it’s your first exposition to number theory, I think I would recommend Elementary Number Theory by Jones and Jones. Much cheaper than Silverman, and just as good.

  3. Windy

    Yes, it is my first exposition to number theory. So in your opinion, H&W is not the best textbook to dive into the topic, albeit a good reference for an advanced number theory course.

    Thank you for your answer, was useful.

    Reply
    1. Firas Post author

      I don’t know of any school where Hardy and Wright is used as a textbook right now for a number theory course of any kind. In addition to being big and dry, it is also somewhat dated. It is nice to have around as a reference, but not as a primary learning source (at least that’s my feeling, of course different people have different tastes).

Leave a Reply

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