I am working through the example in implementation of the quadratic sieve, and I have got stuck at the very last part: the matrix processing. In the example we must find the vector $S$ by left null space.
However if we transpose the matrix A and attempt to apply Gaussian Elimination to find the solution to S as in the example, the resulting solution does not match up with the answer in the example.
What am I missing here? Is the "mod 2" part left out of the null space method or applied later to the resulting solution?
How is the resulting $S$ vector then used in the next two equations we find:
There might be a more instructive way to do this!
We want to find: $S = \left[ \begin{array}{ccc} a & b & c \end{array} \right]$ given $A = \left[ \begin{array}{ccc} 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array} \right]$
such that:
$$ S \cdot A \equiv \left[ \begin{array}{ccc} 0 & 0 & 0 & 0 \end{array} \right] \pmod 2$$
so, multiplying the $S$ and $A$, yields a $3x4$:
$$\tag 1 S \cdot A = \left[ \begin{array}{ccc} 0 & b & c\\ 0 & b & c\\ 0 & b & c\\ a & 0 & c \end{array} \right] \equiv \left[ \begin{array}{ccc} 0 & 0 & 0 & 0 \end{array} \right] \pmod 2$$
From $(1)$, we get a set of modular equations (given that we have three duplicates):
$$ b + c \equiv 0 \pmod 2$$ $$ \tag 2 a + c \equiv 0 \pmod 2$$
So, solving the system in $(2)$ by whatever method you are comfortable with, we get
$$S = \left[ \begin{array}{ccc} a & b & c \end{array} \right] = \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right]$$
This is, apparently, telling us that the product of all 3 equations yields a square$\pmod N$, meaning we use the table they calculated above and take the product of all three factors for both sides from $X + 124$ and $Y$ (table they calculated earlier).
So, forming the product of all three (since we have S with all $1's$), $Y's \equiv$ the product of the three $X + 24's$, yielding, $29 \cdot 782 \cdot 22678 = 22678^2$ and $124^2 \cdot 127^2 \cdot 195^2 = 3070860^2$, and then equating sides, we arrive at:
$$22678^2 \equiv 3070860^2 \pmod {15347}$$
Update:
I am not sure it is a good idea to rely on an example on the Wiki for such a complex algorithm. I just got home and looked in "Prime Numbers, A Computational Perspective", by Crandall and Pomerance. In it, they have spelled out the algorithm and all of the nuances!
You can also find additional examples in these papers on NFS:
NFS 1
NFS 2
Regards