Quadratic Sieve: Gaussian Elimination

Question

I am reading the Quadratic Sieve algorithm from Silverman's mathematical Cryptography book.

I have understood almost everything in the algorithm except the part where he uses Gaussian Elimination to narrow down those numbers which can be tried with the next step to find the factors.

We have the list - I understand how this list is formed.

From this list, he forms the matrix - - I understood the above - how he forms the matrix.

After this he says

The next step is to solve the system of linear equations in Table 3.5. This can be done by standard Gaussian elimination, always keeping in mind that all computations are done modulo 2. The set of solutions turns out to be an F2-vector space of dimension 8. A basis for the set of solutions is given by the following 8 vectors, where we have written the vectors horizontally, rather than vertically, in order to save space:

And then he gets these vectors as the solution

$v1 = (0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0),$

$v2 = (0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0),$

$v3 = (0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0),$

$v4 = (1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0),$

$v5 = (1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0),$

$v6 = (1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0),$

$v7 = (1,0,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,0),$

$v8 = (1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1)$

---

So, we have a Matrix $M_{15X20}$ & a vector with 20 rows. So from these, how do we get 8 vectors each with 20 elements?

Shouldn't we get $u_1$ to $u_{20}$. What exactly are these vectors & how do get to it?

---

I understand basic gaussian elimination to solve Linear Algebra equations - i.e if you have 3 variables (x, y, z) & you have 3 equations, then you can use Gaussian elimination to solve it. I understand how it works, but I usually use SageMath to do it.

M.solve_right(v) - where M is the Matrix & v is the vector.

In this case, since it's mod 2, I will define the Matrix M & vector v in a Ring of 2 & do it. But if I try with the the above matrix & vector in a ring of 2, I just get 1 vector as the answer with 20 elements. And it seems logical because I have a 15x20 Matrix & a 20 element vector. So how is the book doing whatever it's doing?

Answer 1

Though this is clothed in number theory trappings, this is a linear algebra question. At its core, this question is How do we find a basis for the kernel of a linear transformation using Gaussian elimination? Here is one possible answer.

For a smaller example, we might consider the equation $$ A \vec{x} = \vec{0} \tag{1}$$ where $$ A = \left(\begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 \end{array}\right).$$ This is like your equation, except over $\mathbb{C}$ instead of $\mathbb{F}_2$, and smaller dimension. Finding all such $\vec{x}$ is exactly the same as computing the kernel, and Gaussian elimination is very commonly used to find a basis for the kernel. Here, a basis for the kernel are the two vectors $$ v_1 = \left(1,\,0,\,-3,\,2\right), \quad v_2 = \left(0,\,1,\,-2,\,1\right), $$ where I've written them as row vectors, but think of them as column vectors.

All vectors of the form $a v_1 + b v_2$ for any $a, b$ are solutions to $(1)$.

Since you note that you want to compute this in sage, I'll note that you do this with the following:

m = matrix([[1, 2, 3, 4], [1, 1, 1, 1], [0 ,1, 2, 3], [3, 4, 5, 6]])
m.T.kernel()  

An oddity here is using m.T. In sage, m.kernel() gives the left kernel, i.e. the solutions to $\vec x A = \vec 0$. But you've given an equation for the right kernel. Taking the transpose of the matrix first fixes this.

For your particular problem, you can do it in sage with

F = Zmod(2)
m = matrix(F, [
  [1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1],
  [0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1],
  [1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0],
  [0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 1],
  [1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0],
  [0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0],
  [1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0],
  [0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0],
  [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0],
  [0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0],
  [0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0],
])
m.T.kernel()

I'll note that this gives a basis of $8$ vectors for the kernel, though this basis probably isn't the same basis that Hoffstein, Pipher, and Silverman give. Nonetheless, this is sufficient.

I don't think this is deterministic and it might change between versions of sage, but the kernel I got back was generated by $$\begin{align} &\left(1,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,1,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1,\,1,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1\right). \end{align}$$

And somewhat surprisingly, taking the first basis vector is sufficient to factor the number. Explicitly,

# The list of numbers used in PHS
ps = (3129, 3130, 3131, 3166, 3174, 3215, 3313, 3449,
      3481, 3561, 4394, 4425, 4426, 4432, 4442, 4468,
      4551, 4595, 4651, 4684)
basisvector1 = (1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0)
numlist = [v[1] for v in list(zip(basisvector1, ps)) if v[0] == 1]
# numlist = [3129, 3481, 4432, 4442, 4651]

N = 9788111
a = prod(numlist) % N      # a = 5710850

# I redo a bit of the work done earlier in the book, reacquiring the factorization:
# the product below is guaranteed to be a square of an integer by the
# linear algebra above.
b = sqrt(prod([num * num % N for num in numlist])) % N
b = 8758842

gcd(N, a - b)              # 2741

This finds the factor $2741$ of $N = 9788111$ (which factors as $3571 \cdot 2741$).