Stage 3: Linear Algebra

The Goal

After sieving, we have many relations where both norms factor completely over our prime base. Now we need to find subsets of relations whose product is a perfect square on both sides.

For a product to be a perfect square, every prime must appear an even number of times. This transforms our problem into linear algebra over GF(2) — the field with only 0 and 1 where 1 + 1 = 0.

The Exponent Matrix

We build a matrix where:

• Each column is a relation
• Each row is a prime in the factor base
• Entry (p, r) = exponent of prime p in relation r, mod 2

       r0  r1  r2  r3  r4
   2 [  1   0   1   1   0 ]
   3 [  0   1   1   0   1 ]
   5 [  1   1   0   0   1 ]
   7 [  0   0   1   1   0 ]
  11 [  1   0   0   1   1 ]

Finding Dependencies

We want to find vectors v = (v₀, v₁, ...) in GF(2) such that Av = 0. This means the sum of the selected columns (where vᵢ = 1) has all zeros, i.e., every prime exponent sums to even.

We use Gaussian elimination to compute the nullspace of the matrix. If we have more relations than primes, we're guaranteed to find at least one non-trivial dependency.

The Algorithm

1. Reduce the matrix to row echelon form using XOR operations
2. Identify pivot columns and free columns
3. For each free column, construct a nullspace basis vector
4. Each basis vector tells us which relations to multiply together