## The Factorization Of F7: Part 2

### September 17, 2010

In the previous exercise, we wrote RESIDUE, which implements the first half of Morrison and Brillhart’s factorization algorithm based on continued fractions. In today’s exercise, we complete the factorization of F_{7} by writing the ANSWER program, which takes the factored *Q _{n}* and computes a factorization of

*N*.

The math underlying the continued fraction factorization algorithm, which we skipped in the previous exercise, is that we are searching for *x* and *y* such that *x*^{2} ≡ *y*^{2} (mod *N*) with *x* ≢ *y* (mod *N*). The convergents of the continued fraction expansion of √*N* have the property that *A*_{n−1} and *Q _{n}*, as defined in the previous exercise, will indicate a factor of

*N*whenever

*Q*is a perfect square, as we saw in the example of

_{n}*Q*

_{52}in the expansion of √13290059. But such

*Q*are rare, which is why the method of Lehmer and Powers never found favor. Much more common is the case that two or more

_{n}*Q*multiply to a perfect square, as they share some odd-power prime factors that, when multiplied together, become an even power.

_{n}Consider the example of the previous exercise. The product of *Q*_{5}, *Q*_{22} and *Q*_{23} is the perfect square 2050 · 4633 · 226 = 2146468900 = 46330^{2} = (2 · 5 · 41 · 113)^{2}. The product of the corresponding *A*_{n−1} is 171341 · 5235158 · 1914221 = 1717050890347212038 ≡ 1469504 (mod 13290059), and we have the congruence (171341 · 5235158 · 1914221)^{2} ≡ (2 · 5 · 41 · 113)^{2} (mod 13290059) or 1469504^{2} ≡ 46330^{2} (mod 13290059). Thus a factor of *N* = 13290059 is GCD(1469504 − 46330, 13290059) = 4261 and *N* = 3119 · 4261.

ANSWER uses the Gaussian elimination algorithm of linear algebra to find a set of *Q _{n}* (Morrison and Brillhart call it an S-set) with product a perfect square. The primes in the factorizations of the

*Q*are 2, 31, 41, 43, 53 and 113, and we also need −1, as there is an implied factor of −1 attached to each

_{n}*Q*with odd

_{n}*n*. Thus, any

*Q*can be represented as a vector of the powers of the exponents of its factors, modulo 2; for instance,

_{n}*Q*

_{5}, with odd-power factors 2 and 41, is represented by the vector [1 1 0 1 0 0 0]. Associated with each exponent vector is a history vector that records our work, which initially has 0 everywhere except 1 in the ordinal position corresponding to the row with which it is associated. Here are the exponent matrix, on the left, and history matrix, on the right, corresponding to the seven

*Q*of our example problem; the columns of the exponent matrix are factors, left to right from low to high, starting with -1, the columns of the history matrix are

_{n}*Q*, left to right from low to high, and the rows of both matrices are

_{n}*Q*, top to bottom from low to high:

_{n}1 1 0 1 0 0 0 1 0 0 0 0 0 0

0 0 1 0 1 0 0 0 1 0 0 0 0 0

0 0 0 1 0 0 1 0 0 1 0 0 0 0

1 1 0 0 0 0 1 0 0 0 1 0 0 0

0 1 1 0 0 1 0 0 0 0 0 1 0 0

1 1 0 0 0 0 1 0 0 0 0 0 1 0

0 1 0 0 1 1 0 0 0 0 0 0 0 1

Once the exponent matrix and history matrix are established, the reduction procedure, which performs the forward step of Gaussian elimination, is done as follows:

For each column in the exponent matrix, working from right to left:

Find the “pivot” vector of smallest subscript (nearest the top) whose rightmost 1 is in the current column. If none exists, continue working on the next column to the left.

For each other vector with rightmost 1 in the current column:

Replace the exponent vector with the element-wise sum, modulo 2, of the pivot vector and the current vector.

Replace the associated history vector with the element-wise sum, modulo 2, of the pivot vector and the current vector.

The reduction of the initial matrices given above is shown below:

1 1 0 1 0 0 0 1 0 0 0 0 0 0

0 0 1 0 1 0 0 0 1 0 0 0 0 0

0 0 0 1 0 0 1 0 0 1 0 0 0 0

0 0 0 0 0 0 0 1 0 1 1 0 0 0

0 1 1 0 0 1 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1 0 1 0 0 1 0

0 0 0 0 0 0 0 0 1 0 0 1 0 1

Each of the three rows with zero exponent vectors represents an S-set. Some of those S-sets lead to factorizations, but others fail. For instance, the S-set in the seventh row of the reduced matrix gives the congruence (6700527 · 11455708 · 3213960)^{2} ≡ (2 · 31 · 43 · 53)^{2} (mod 13290059), or 141298^{2} ≡ 141298^{2} (mod 13290059), which is useless. The S-set in the sixth row gives the congruence (171341 · 5235158 · 1895246)^{2} ≡ (2 · 5^{2} · 41 · 113)^{2} (mod 13290059), or 13058409^{2} ≡ 231650^{2} (mod 13290059); however, GCD(13058409 − 231650, 13290059) = 1 and the factorization fails. However, the S-set in the fourth row gives a completed factorization, as shown above.

Your task is to write the ANSWER program described above, and then to find the factors of F_{7} using the factor base and residues from the previous exercise. When you are finished, you are welcome to read, run or print a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[...] (mod n), it is likely that gcd(x-y, n) will be a factor of n. The algorithm is similar to the CFRAC algorithm of Morrison and Brillhart: the first phase finds smooth relations, and the second phase uses linear [...]