Last Steps of the Quadratic Sieve (Matrix Onwards)

[My Name Is D]

Homework Statement

Hi. I've got the matrix from the Quadratic Sieve down to Gaussian Form and I'm wondering how to find the factor base which leads to a square number now.

Homework Equations

The Factor Base:
$${29,782,22678}$$
The original Matrix:
\begin{pmatrix}
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1\\
\end{pmatrix}

The Attempt at a Solution

The Matrix after being transposed and Gaussian Elimination:
\begin{pmatrix}
1 & 0 & 1\\
0 & 1 & 1\\
0 & 0 & 0\\
0 & 0 & 0
\end{pmatrix}
I know I have to relate this back to the factor base somehow? I can see that $$29*782*22678 = 514291684 = 22678^2$$ But how does that relate to the matrix? I'm trying to implement it in Java and am using the Matrix package JAMA for computations. Any help would be much appreciated!

 

[Joffan]

You're looking for a combination of the rows which produces all even numbers (which, since this matrix is exponents, corresponds to a square number). Working mod 2, that's all zeros.

This set is "lucky" to have a solution at only three rows and four columns, but generally there will be a suitable subset if there are more rows than columns.

I think you can just eliminate down from the top, picking the first non-zero column in each row and xor-ing to any rows below that have 1 in that column, and keeping track of which rows have been summed in each case. Of course if I add row 1 into rows 3 and 4, and I later add rows 3 and 4, I have eliminated row 1 from that sum because adding twice is the same as not adding at all, working mod 2.

In your particular case, the numbers are coded in the matrix by the exponents of 2, 17, 23 and 29. Adding all three rows means that the product of the three numbers has exponents of 2, 2, 2 and 2 for those primes and is thus the square of 2*17*23*29.

[ for this example, which is actually worked in Wikipedia, http://en.wikipedia.org/wiki/Quadratic_sieve , there is actually another row that could be in the matrix: 0, 0, 2, 0 :but of course this works on its own without combining with any other row, so does not illustrate the method. I found a similar issue when trying out 559423. Note that dividing out the base primes should be exhaustive when sieving - if dividing out 7, for example, do it repeatedly, and keep track of the total factor count separately from your mod 2 elimination matrix. ]

 

[Joffan]

Specifically on what to do to find the suitable combination, you could do a form of Gaussian elimination on the originally orientated matrix

Start state:
Exponents (corresponding to powers of 2, 17, 23 and 29, for 29, 782 and 22678)
\begin{pmatrix}
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1\\
\end{pmatrix}
Row-sum tracker (initially identity matrix)
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}

Find non-zero entry for row 1 @ column 4, xor to lower rows with non-zero column 4:
\begin{pmatrix}
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 0\\
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1 \\
\end{pmatrix}

Find non-zero entry for row 2 @ column 1, xor to lower rows with non-zero column 1:
\begin{pmatrix}
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
0 & 0 & 0 & 0\\
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 1 & 1 \\
\end{pmatrix}

Find only zero entries for row 3, read combination rows from tracking matrix for result
\begin{pmatrix}
1 & 1 & 1 \\
\end{pmatrix}
which implies that all three smooth values multiplied together will satisfy the conditions.

For additional trials you might like to use 559423, 6378971 and 7171537

 

[My Name Is D]

Thanks a lot Joffan! One question, when conducting the special Gaussian elimination, do you not need to eliminate the value you are currently using as a pivot once all lower rows have been XOR'd?

 

[Joffan]

No, I think that would be confusing. As it stands, each row of the tracker matrix indicates the combination of rows in the original exponent-mod-2 matrix that was used for that row of the modified matrix.

The final outcome is some all-zero rows. They're what we're after.

 

[My Name Is D]

Thanks, do you also need to XOR for all values of 1 in a row or does it suffice to check for just the first one?

 

[Joffan]

You XOR the whole row, but only for other rows that have a one in the pivot column. Unfortunately this example is really too small to see that, so I put a slightly larger (completely made-up) example below.

The first entry of one is just an arbitrary choice. Any entry of one will work, I was just keeping it easy to remember.

$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 \\ <br /> 1 & 1 & 0 & 1 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> 1 & 0 & 0 & 0 \\ <br /> \end{pmatrix} ||<br /> \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 0 \\ <br /> 0 & 0 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$

$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 \\ <br /> 1 & 0 & 0 & 0 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> 1 & 0 & 0 & 0 \\ <br /> \end{pmatrix} ||<br /> \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 \\ <br /> 1 & 0 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 0 \\ <br /> 0 & 0 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$

$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> \end{pmatrix} ||<br /> \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 \\ <br /> 1 & 1 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 0 \\ <br /> 0 & 1 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$

$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 \\ <br /> 0 & 0 & 1 & 1 \\ <br /> 0 & 0 & 0 & 0 \\ <br /> 0 & 0 & 0 & 0 \\ <br /> \end{pmatrix} ||<br /> \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 \\ <br /> 1 & 1 & 1 & 0 & 0 \\ <br /> 1 & 1 & 1 & 1 & 0 \\ <br /> 1 & 0 & 1 & 0 & 1 \\ <br /> \end{pmatrix}$

 

[My Name Is D]

If it's not too much trouble, could you work through a full example? I'm having trouble getting my program to work correctly. Very few of the values it generates for all zero rows are squares, and when they are, they tend to not lead to factors once the GCD is calculated. I am using small test numbers too - up to 1000.

 

[Joffan]

The values derived from all zero rows cannot be anything but squares. However sometimes (with small values, anyway) they may not give you the factors you are looking for, because the values derived are equal or sum to N.

Looking at 13987, and using the first six primes where that is a quadratic root: 2, 3, 7, 13, 17, 23, I get seven smooth numbers corresponding to numbers between 119 and 167: 122, 125, 127, 131, 134, 145 and 161, whose squares mod 13987 are 897, 1638, 2142, 3174, 3969, 7038, 11934, all of which are composed only of the above prime factors. I discarded 134 & 3969 because 3969 = 63² (a square, so not interesting for this exercise), giving the following factor exponent matrix:

\begin{pmatrix}
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 2 & 1 & 1 & 0 & 0 \\
1 & 2 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 2 \\
1 & 2 & 0 & 0 & 1 & 1 \\
1 & 3 & 0 & 1 & 1 & 0 \\
\end{pmatrix}

Reducing this matrix mod 2, the elimination goes as follows:

$$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 & 0 & 0 \\ <br /> 1 & 0 & 1 & 0 & 1 & 0 \\ <br /> 1 & 1 & 0 & 0 & 0 & 0 \\ <br /> 1 & 0 & 0 & 0 & 1 & 1 \\ <br /> 1 & 1 & 0 & 1 & 1 & 0 \\ <br /> \end{pmatrix} || \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 0 & 1 & 0 \\ <br /> 0 & 0 & 0 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$$

xor row 1 to rows 4 and 6

$$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 & 0 & 0 \\ <br /> 1 & 0 & 1 & 0 & 1 & 0 \\ <br /> 1 & 0 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 0 & 0 & 1 & 1 \\ <br /> 1 & 0 & 0 & 0 & 1 & 1 \\ <br /> \end{pmatrix} || \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 & 0 \\ <br /> 1 & 0 & 0 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 0 & 1 & 0 \\ <br /> 1 & 0 & 0 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$$

xor row 2 to rows 3,4,5,6

$$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 1 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 & 1 \\ <br /> 0 & 0 & 1 & 1 & 1 & 1 \\ <br /> 0 & 0 & 1 & 1 & 1 & 1 \\ <br /> \end{pmatrix} || \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 1 & 0 & 0 & 0 \\ <br /> 1 & 1 & 0 & 1 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 1 & 0 \\ <br /> 1 & 1 & 0 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$$

xor row 3 to rows 5 & 6

$$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 1 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 & 1 \\ <br /> 0 & 0 & 1 & 0 & 0 & 1 \\ <br /> 0 & 0 & 1 & 0 & 0 & 1 \\ <br /> \end{pmatrix} || \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 1 & 0 & 0 & 0 \\ <br /> 1 & 1 & 0 & 1 & 0 & 0 \\ <br /> 0 & 0 & 1 & 0 & 1 & 0 \\ <br /> 1 & 0 & 1 & 0 & 0 & 1 \\ <br /> \end{pmatrix}$$

xor row 4 to rows 5 & 6

$$\begin{pmatrix}<br /> 0 & 1 & 0 & 1 & 0 & 1 \\ <br /> 1 & 0 & 1 & 1 & 0 & 0 \\ <br /> 0 & 0 & 0 & 1 & 1 & 0 \\ <br /> 0 & 0 & 1 & 0 & 0 & 1 \\ <br /> 0 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 0 & 0 & 0 & 0 & 0 \\ <br /> \end{pmatrix} || \begin{pmatrix}<br /> 1 & 0 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 0 & 0 & 0 & 0 \\ <br /> 0 & 1 & 1 & 0 & 0 & 0 \\ <br /> 1 & 1 & 0 & 1 & 0 & 0 \\ <br /> 1 & 1 & 1 & 1 & 1 & 0 \\ <br /> 0 & 1 & 1 & 1 & 0 & 1 \\ <br /> \end{pmatrix}$$

This gives us two all-zero rows and hence two solutions (which both work): combine the first five numbers, or combine the 2nd, 3rd, 4th and 6th (reading from the corresponding rows of the tracker). This means going back to the original factor exponents above - the mod-2 matrix shouldn't be used for the final calculation.

So taking the first of these, 811 == (122*125*127*131*145) mod 13987 and 897*1638*2142*3174*7038*11934 is a square whose root 265149612 == 12040 mod 13987.
GCD(13987,12040-811) = 197
GCD(13987,12040+811) = 71

 

[My Name Is D]

Thanks! It's now at least working! :) Is there any documentation you can refer me to for choosing good values for the size of the sieve and what to use as β for the smoothness bound?

Again, much appreciated.

Also, I am now trying numbers > 20 digits long and the method seems to have broken down as the matrix doesn't produce 0 rows anymore. I think this is down to do with having more columns than rows

 

[Joffan]

Yep. You need more rows than columns to be sure of getting a zero row, and it's better to get several. So just keep sieving until you have enough candidates. While I'm sure there will be some guidance out there, the discussion of polynomial forms in Wikipedia suggests that straight prime searches of the type we've been doing here won't be sufficient (or not efficient, anyway) for large numbers.

I don't know enough about the subject to recommend anything at high numbers. Pomerance's 1996 paper http://www.ams.org/notices/199612/pomerance.pdf (from Wikipedia) is readable and give some additional references.

I neglected to mention that the 134/3969 combo in my example, while not illustrating the elimination phase, is actually the most direct route to the answer, so would be very interesting if encountered in a real factoring problem.

ETA: http://www.cs.virginia.edu/crab/QFS_Simple.pdf seems good.