Register to reply 
Last Steps of the Quadratic Sieve (Matrix Onwards) 
Share this thread: 
#1
Jan712, 09:49 AM

P: 5

1. The problem statement, all variables and given/known data
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. 2. Relevant 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} 3. 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! 


#2
Jan1012, 07:35 PM

P: 361

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 nonzero column in each row and xoring 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. ] 


#3
Jan1112, 01:06 PM

P: 361

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} Rowsum tracker (initially identity matrix) \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} Find nonzero entry for row 1 @ column 4, xor to lower rows with nonzero 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 nonzero entry for row 2 @ column 1, xor to lower rows with nonzero 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 


#4
Jan1312, 06:18 AM

P: 5

Last Steps of the Quadratic Sieve (Matrix Onwards)
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?



#5
Jan1312, 09:16 AM

P: 361

No, I think that would be confusing. As it stands, each row of the tracker matrix indicates the combination of rows in the original exponentmod2 matrix that was used for that row of the modified matrix.
The final outcome is some allzero rows. They're what we're after. 


#6
Jan1512, 11:40 AM

P: 5

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?



#7
Jan1512, 02:25 PM

P: 361

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 madeup) 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. [itex] \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} [/itex] [itex] \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} [/itex] [itex] \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ \end{pmatrix} [/itex] [itex] \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix} [/itex] 


#8
Jan1512, 05:37 PM

P: 5

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.



#9
Jan1612, 01:58 AM

P: 361

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^{2} (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: [tex] \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} [/tex] xor row 1 to rows 4 and 6 [tex] \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} [/tex] xor row 2 to rows 3,4,5,6 [tex] \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} [/tex] xor row 3 to rows 5 & 6 [tex] \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ \end{pmatrix} [/tex] xor row 4 to rows 5 & 6 [tex] \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}  \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ \end{pmatrix} [/tex] This gives us two allzero 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 mod2 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,12040811) = 197 GCD(13987,12040+811) = 71 


#10
Jan1612, 02:16 PM

P: 5

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 


#11
Jan1612, 10:03 PM

P: 361

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. 


Register to reply 
Related Discussions  
Matrix of a quadratic form  Calculus & Beyond Homework  1  
Can Somebody Explain These Steps for Me(answer given, dont get steps in between)  Advanced Physics Homework  1  
How is a nonquadratic matrix singular?  Linear & Abstract Algebra  18  
Momentum questions  ALevel onwards standard (formulas and explanations needed)  Introductory Physics Homework  9  
Quadratic Matrix Equation  Linear & Abstract Algebra  0 