Quadratic Sieve by Hand

[Sam Kennedy]

I've changed the "gaussian elimination" algorithm, after finding a 1 in the first column, and doing the elimination, I swap the (pivot?) row with the top row.

However the algorithm just runs and runs, without finding any zero vectors.

[bsquared]

Originally Posted by Sam Kennedy

Here is a summary of what my program does:
-Input n
-Input smoothness bound (upper limit for factor base)
-Use sieve of Eratosthenes to create factor base
-Starting at the ceiling of the square root of n (let's call the value r), calculate r^2 mod n
-Divide r repeatedly by each factor in the factor base, if the value is 1, save r, otherwise increment and start again, until there are as many values of r as in the factor base, plus one
-Create vector matrix
-Do my horrible version of gaussian elimination
-Check for zero vectors, then attempt to factor, if no zero vectors, do gaussian elimination again
-Use gcd to factor number

-

Gaussian elimination woes aside, what you described above isn't the quadratic sieve. It's closer to Dixon's algorithm than anything because you are not sieving to find smooth numbers. Dixon's algorithm trial divides integers Q = r^2 mod N for random r near sqrt(N). Your 'r' values aren't random but the effect is the same and as a result the method will be very slow.

See here.

Sieving involves first solving congruences of the form x^2 == n mod p for each prime p in the factor base. Also, each prime p in the factor base should be a quadratic residue mod n. I'm not sure if you've placed this restriction on your factor base or not, but you should. You can conduct quadratic residue tests using the Legendre symbol, and there are various methods for solving quadratic congruences.

[Dubslow]

Okay, lets try this from the top.

First, watch the first 14:30 of this lecture about Gaussian elimination. He talks about it in the context of solving systems of equations, but our use case is slightly different.* (The rest of the lecture is about other, perhaps more common/useful applications of elimination, but aren't necessary for QS purposes.)



AFTER you've watched the first 14:30:

What he demonstrates is elimination on a square matrix, reducing it to an upper triangular matrix (i.e., zeros below all pivots, for an arbitrary (non-square) matrix it's called row echelon form). In our case, we need the reduced row echelon form. We do this by performing Gauss-Jordan elimination, which is the same except that we keep going after row echelon form. Instead of eliminating below the pivots, we know eliminate above the pivots, starting with the very last row/pivot/equation. (So it's as if we rotate the matrix 180 degrees and do Gaussian elimination over again; in the terminology of the lecture, we do backwards elimination after having done forward elimination.)

After this is done, we can read the nullspace off of the reduced row echelon form of the matrix. (By the way, we don't need to augment our matrix with the identity matrix and track that -- that's how we compute the inverse, but that's not what we're trying to do.)

Actually, just watch this second lecture (this time, the entirety of it). I couldn't remember how to read the nullspace off the rref form of the matrix, so I watched it myself, but there's little point in me writing it down when you can watch it yourself. (He's good at explaining things.)

____________________________________________________________________________________________________________________

Originally Posted by bsquared

Gaussian elimination woes aside, what you described above isn't the quadratic sieve. It's closer to Dixon's algorithm than anything because you are not sieving to find smooth numbers. Dixon's algorithm trial divides integers Q = r^2 mod N for random r near sqrt(N). Your 'r' values aren't random but the effect is the same and as a result the method will be very slow.

See here.

Isn't it somewhat analogous to the difference between trial dividing to create a list of primes, vs. something like sieve of Eratosthenes?

Originally Posted by bsquared

Sieving involves first solving congruences of the form x^2 == n mod p for each prime p in the factor base. Also, each prime p in the factor base should be a quadratic residue mod n. I'm not sure if you've placed this restriction on your factor base or not, but you should. You can conduct quadratic residue tests using the Legendre symbol, and there are various methods for solving quadratic congruences.

Guess what we just started in my number theory class?

[Sam Kennedy]

I did have a section of code which only allowed primes with a legendre symbol of +1 to be in the factor base, but I found this reduced the size of the factor base quite a bit, and it was harder to get an n by n+1 matrix.

My problem with the 'real' sieve is that I don't know how much data to collect before running the sieve, I might end up with too few values.

I guess my code needs a complete overhaul, follow the method properly, then I can worry about entering the correct parameters later

Thank you for the links to those video lectures, the first one really cleared up what I'm supposed to be doing, I'm about to watch the second one now :)

For solving the quadratic congruences, could I use this function?

Function: int mpz_invert (mpz_t rop, mpz_t op1, mpz_t op2)
Compute the inverse of op1 modulo op2 and put the result in rop.

[Yah]

I'm trying to understand how this matrix thing works and I think I've got it until the backwards elimination.
Let's take this for example :
N=2041
FB=2,3,5,7

So, starting from (sqroot N) ^ 2 - N I get this values :

168 -> 47
360 -> 49
768 -> 53
1440 -> 59

ok, so without using matrix I can solve this by 368x1440 = 518400 which is a square (720) mod N (2041) = 720 , then 49x59 = 2891 mod N (2041) = 850
then finding factors gcd(850+720,2041) = 157 , gcd(850-720,2041) = 13

Now, solving that via matrix is what I can't figure out quite right.

So I build matrix like this (168 is the first row (3101), then 360 etc.) :
3 1 0 1
3 2 1 0
8 1 0 0
5 2 1 0

mod 2 :
1 1 0 1
1 0 1 0
0 1 0 0
1 0 1 0

with identity on the right it should be like this :
1101 1000
1010 0100
0100 0010
1010 0001

From what I could figure out from this thread now I start by adding rows with 1 in the first column, so without me writing down all those operations from top to bottom this is what I get in the end :

1101 1000
0111 1100
0100 0010
0111 1001

And this is where I'm stuck and don't know really how to continue.

Also I'm not sure whether identity matrix on the right should even be used or not (from Dubslow post above)

(By the way, we don't need to augment our matrix with the identity matrix and track that -- that's how we compute the inverse, but that's not what we're trying to do.)

Anyway, with identity matrix or not, can someone please explain to me how to solve the above example with matrix elimination, if I got all the steps right up to the point where I stopped above (backward elimination should come next) how do I continue exactly ?

Thanks.

[LaurV]

Your goal is to get a line to be all zeros in the matrix (see post #2). For this, usually you need more lines then columns.

N=2041
FB=2,3,5,7

int(sqrt(n))=45 (I will use code tag for alignment)

46^2 =  75 = 2^0 * 3^1 * 5^2 * 7^0 (mod 2041)
47^2 = 168 = 2^3 * 3^1 * 5^0 * 7^1 (mod 2041)
49^2 = 360 = 2^3 * 3^2 * 5^1 * 7^0 (mod 2041)
51^2 = 560 = 2^4 * 3^0 * 5^1 * 7^1 (mod 2041)
53^2 = 768 = 2^8 * 3^1 * 5^0 * 7^0 (mod 2041)

So, your (binary) matrix is:

0,1,0,0
1,1,0,1
1,0,1,0
0,0,1,1
0,1,0,0

You put the identity on the right (the identity represent how many times you considered/added each equation, and it is a 5x5 matrix), and after a couple of additions you get (one possibility, remember the goal is to get a line of zeroes on the left)

0,1,0,0 | 1,0,0,0,0
1,1,0,1 | 0,1,0,0,0
1,0,1,0 | 0,0,1,0,0
0,0,1,1 | 0,0,0,1,0
0,1,0,0 | 0,0,0,0,1
==>
(added second line to the first to get a 1 in first col, you could get that by sorting too, but we talk about concept, not optimization)
1,0,0,1 | 1,1,0,0,0
1,1,0,1 | 0,1,0,0,0
1,0,1,0 | 0,0,1,0,0
0,0,1,1 | 0,0,0,1,0
0,1,0,0 | 0,0,0,0,1
==>
(added first line to all which have 1 in first column, to get rid of the 1's)
1,0,0,1 | 1,1,0,0,0
0,1,0,0 | 1,0,0,0,0
0,0,1,1 | 1,1,1,0,0
0,0,1,1 | 0,0,0,1,0
0,1,0,0 | 0,0,0,0,1
==>
1,0,0,1 | 1,1,0,0,0
0,1,0,0 | 1,0,0,0,0
0,0,1,1 | 1,1,1,0,0
0,0,1,1 | 0,0,0,1,0
0,0,0,0 | 1,0,0,0,1
==>
1,0,0,1 | 1,1,0,0,0
0,1,0,0 | 1,0,0,0,0
0,0,1,1 | 1,1,1,0,0
0,0,0,0 | 1,1,1,1,0
0,0,0,0 | 1,0,0,0,1

So, if you multiply first 4 together, or the first and the last one (this you see from the right side, of course you can stop when you get first red line, I continued one step more for clarity) then you get a square. From here is solving by congruences of squares.

(46*56)^2=(2^4*3*5)^2
397^2-240^2=0 (mod 2041)
gcd(397-240,2041)=157
gcd(397+240,2041)=13

[jasonp]

Another way to think about LaurV's example is that when you've changed the matrix on the left to have one or more rows of all-zero, the value of the corresponding solution variable can be anything and all the other rows will still wok. So in his example you can set the last two variables of the solution to random 0 or 1 bits, then proceed with the back substitution to find what the other rows should be once the last two variables have been chosen.

The result is a vector in the nullspace of the matrix. An advantage of this method is that you don't have to track any right-hand-side matrix while the elimination is in progress.

[Yah]

Originally Posted by LaurV

(added first line to all which have 1 in first column, to get rid of the 1's)
1,0,0,1 | 1,1,0,0,0
0,1,0,0 | 1,0,0,0,0
0,0,1,1 | 1,1,1,0,0
0,0,1,1 | 0,0,0,1,0
0,1,0,0 | 0,0,0,0,1
==>
1,0,0,1 | 1,1,0,0,0
0,1,0,0 | 1,0,0,0,0
0,0,1,1 | 1,1,1,0,0
0,0,1,1 | 0,0,0,1,0
0,0,0,0 | 1,0,0,0,1

Okay, everything is clear now except this part above, after you added first line to all the rows which have 1 in the first column, what was the next step which gave you all the zeros in the last row ? You move to the next pivot and look now for 1's in the second column ? From the example above that seems to be the case, but just to clarify the steps.

[LaurV]

Originally Posted by Yah

after you added first line to all the rows which have 1 in the first column, what was the next step which gave you all the zeros in the last row ?

-added second line to all the rows below it which have 1 in the second column, to get rid of the ones in the second column (all lines after and including the second have 0 on the first column)
-added third line to all the rows below it which have 1 in the third column, to get rid of the ones in the third column (all lines after and including the third have 0 on the first 2 columns)
-.....
-added n-th line to all the rows below it which have 1 in the n-th column, to get rid of the ones in the n-th column (all lines after and including the n-th have 0 on the first n-1 columns).

After you do the n-th step, all rows below the n-th are all zero on the left. That is why you need more then n rows. This is how the Gauss elimination works (well, particularized for this thing).

[Yah]

I understand, thank you very much sir.