Modern Factoring Methods
The Quadratic Sieve: Linear Algebra Stage
Finding dependencies in the relation matrix over the field with two elements, and why this stage is the practical bottleneck.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0675
Relations are combined into a congruence of squares by finding dependencies in a large sparse matrix over the field with two elements. This stage is where large factorisations most often become impractical.
The matrix
Rows are relations, columns are factor base primes, entries are exponents reduced modulo two. A kernel vector identifies a subset of relations whose product is a perfect square.
Matrix characteristics
Why elimination fails
The methods used
| Method | Character | Note |
|---|---|---|
| Structured elimination | Preprocessing | Removes singletons and light rows; shrinks the matrix substantially |
| Block Lanczos | Iterative | Preserves sparsity; the common choice |
| Block Wiedemann | Iterative | Distributes better across machines |
| Dense elimination | Final step | Applied only to the small dense residue |
The parallelism problem
From dependency to factor
Extracting the factor
- Take a kernel vectorIdentifying a subset of relations.
- Form the two sidesThe product of the relation values, and the product of the corresponding roots.
- Take square rootsOf the factor base side, using the known exponent vector.
- Take a GCDOf the difference with the target.
- Retry if trivialAbout half of dependencies give a trivial factor; use the next kernel vector.
The same problem elsewhere
Class group computation has an identical linear algebra stage, over the integers rather than the field with two elements — see relation matrix construction and Smith normal form.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.