Slovak University of Technology, Bratislava
Faculty of Electrical Engineering and Information Technology
Degree Course: INFORMATICS
Author: Bc. Martin Pilka
Diploma thesis: Linear aspects of factorization
Supervisor: doc. RNDr. Ladislav Satko, PhD.
2003, May

Factorization algorithms based on congruences of squares require finding linear dependent sets of vectors over GF(2) in a sparse MxN matrix (Linear Algebra Step of factorization process). We explain how to obtain these linear dependent sets using Gauss Elimination. We examine how matrix density changes during Linear Algebra Step and use this knowledge to reduce memory requirements. We describe several modifications of basic algorithm and compare their performance. We also examine several approaches on how to assemble semifull relations from partial relations (Large Prime Variation). We provide C++ implementation of Multiple Polynomial Quadratic Sieve with distributed sieving phase (including source code) and demonstrate proposed algorithms on factorization of 50-110 digits long RSA numbers.