Skip to main content

Parallel Solution of Sparse Linear Systems Defined Over GF(p)

Dan Page, Parallel Solution of Sparse Linear Systems Defined Over GF(p). CSTR-05-003, University of Bristol. November 2004. PDF, 257 Kbytes.

Abstract

The second stage of processing in the Number Field Sieve (NFS) and Function Field Sieve (FFS) algorithms when applied to discrete logarithm problems requires the solution of a large, sparse linear system defined over a finite field. This operation, although well studied in theory, presents a practical bottleneck that can limit the size of problem either algorithm can tackle. In order to partially bridge this gap between theory and practise, we investigate and develop a fast, scalable implementation of the Lanczos algorithm over GF(p) that can solve such systems in parallel using workstation clusters and dedicated Beowulf clusters.

Bibtex entry.

Contact details

Publication Admin