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 F7 by writing the ANSWER program, which takes the factored Qn 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 x2y2 (mod N) with xy (mod N). The convergents of the continued fraction expansion of √N have the property that An−1 and Qn, as defined in the previous exercise, will indicate a factor of N whenever Qn is a perfect square, as we saw in the example of Q52 in the expansion of √13290059. But such Qn are rare, which is why the method of Lehmer and Powers never found favor. Much more common is the case that two or more Qn multiply to a perfect square, as they share some odd-power prime factors that, when multiplied together, become an even power.

Consider the example of the previous exercise. The product of Q5, Q22 and Q23 is the perfect square 2050 · 4633 · 226 = 2146468900 = 463302 = (2 · 5 · 41 · 113)2. The product of the corresponding An−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 14695042 ≡ 463302 (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 Qn (Morrison and Brillhart call it an S-set) with product a perfect square. The primes in the factorizations of the Qn are 2, 31, 41, 43, 53 and 113, and we also need −1, as there is an implied factor of −1 attached to each Qn with odd n. Thus, any Qn can be represented as a vector of the powers of the exponents of its factors, modulo 2; for instance, Q5, 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 Qn 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 Qn, left to right from low to high, and the rows of both matrices are Qn, top to bottom from low to high:

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 1412982 ≡ 1412982 (mod 13290059), which is useless. The S-set in the sixth row gives the congruence (171341 · 5235158 · 1895246)2 ≡ (2 · 52 · 41 · 113)2 (mod 13290059), or 130584092 ≡ 2316502 (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 F7 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.

About these ads

Pages: 1 2 3

One Response to “The Factorization Of F7: Part 2”

  1. [...] (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 [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: