Quadratic Sieve
I am attempting to program the Quadratic Sieve algorithm for factoring large composite numbers. I have selected my composite number to be factored, $n$: \begin{align} n = 87463 \end{align}
I have completed the sieving phase and am now onto the linear algebra phase. Per my instructions, I have created a matrix, $M$, comprised of exponents and reduced its elements by $\pmod 2$.
\begin{pmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{pmatrix}
I have converted M to reduced echelon form. I am searching for an algorithm to generate solution vectors, λ, such that λ ⋅ M = 0 (mod 2).
\begin{pmatrix} 1 & 1 & 1 & 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 \\ \end{pmatrix}
I know that the solution vector, $\lambda$, is comprised of $0$'s and $1$'s, where there must be at least two $1$'s (or else the vector won't be useful in factorization process). The follow vector is a valid solution, but isn't useful in factoring $n$.
\begin{pmatrix} 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}
I am sorry if any of this is misconstrued/incorrect, I am still very confused myself. I can provide any extra details if needed, thanks in advance!
Edit: Here is the console output from my latest attempt. If you can spot any errors in my process, please let me know because right now the generated $x$ & $y$ values are incorrect.
Number to be factored, n=87463.
Size of the factor base, B=14.
The primes in the factor base: [-1, 2, 3, 13, 17, 19, 29].
The number of primes in the factor base, K=6.
[1, 1, 2, 0, 0, 0, 0]
Sieve Results (x-value, x^2-n, vector of exponents):
296 153 [0, 0, 2, 0, 1, 0, 0]
299 1938 [0, 1, 1, 0, 1, 1, 0]
307 6786 [0, 1, 2, 1, 0, 0, 1]
278 -10179 [1, 0, 3, 1, 0, 0, 1]
316 12393 [0, 0, 6, 0, 1, 0, 0]
265 -17238 [1, 1, 1, 2, 1, 0, 0]
M = 6 X 7
Created from the sieving process (rows are exponents from above)
0 0 2 0 1 0 0
0 1 1 0 1 1 0
0 1 2 1 0 0 1
1 0 3 1 0 0 1
0 0 6 0 1 0 0
1 1 1 2 1 0 0
M modulo 2
0 0 0 0 1 0 0
0 1 1 0 1 1 0
0 1 0 1 0 0 1
1 0 1 1 0 0 1
0 0 0 0 1 0 0
1 1 1 0 1 0 0
Transposed M
0 0 0 1 0 1
0 1 1 0 0 1
0 1 0 1 0 1
0 0 1 1 0 0
1 1 0 0 1 1
0 1 0 0 0 0
0 0 1 1 0 0
Reduced Row Echelon Form
1 0 0 0 1 1
0 1 0 0 0 0
0 0 1 0 0 1
0 0 0 1 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Solution vector: [0, 0, 1, 1, 1, 1]
x = 83740
y = 14616
gcd(x-y, n) = 1
Here are the formulas I'm using to generate $x$ & $y$:
$$x = \prod_{i=1}^{K+2} x_i^{\lambda_i} \pmod n$$
$$y = \prod_{i=1}^{K+2} (x_i^2-n)^{\lambda_i/2} \pmod n$$
If $\lambda \cdot M = 0 \pmod{2}$, it means
$\lambda_1=0$ and $\lambda_5=0$ and there are no restriction on the other entries.
$$\lambda = (0,a,b,c,0,d)$$
You have the freedom to choose $a,b,c,d\in \{ 0,1\}$ and they are valid solution to the system $\lambda \cdot M =0 \pmod{2}.$
Edit:
It seems initially you want to solve $\lambda \cdot M = 0$,
after which a transpose is taken: $$M^T \cdot \lambda^T = 0$$
and we reduce $M^T$ to reduce row echelon form, call it $R$.
$$R \cdot \lambda^T = 0$$
where
For $$R = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix} $$
The first $4$ variables are pivot variable and the remaining $2$ are not.
We get to select $\lambda_5$ and $\lambda_6$ and we have
$$\lambda_1 = \lambda_5 + \lambda_6.$$ $$\lambda_2 = 0$$ $$\lambda_3 = \lambda_6$$ $$\lambda_4 = \lambda_6$$