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 *M*x*N* 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.