×

A pipeline architecture for factoring large integers with the quadratic sieve algorithm. (English) Zbl 0644.10002

The authors describe a special architecture to execute the quadratic sieve algorithm for factoring large integers. In the first sections the quadratic sieve algorithm is explained and many optimizations are discussed. The architecture makes use of these optimizations. The quadratic sieve algorithm has roughly three stages: initializing, generating a matrix and reducing this matrix. The special architecture, a pipeline, is designed for the middle (most time consuming) stage. In fact a large range of candidate rows of the matrix will be considered concurrently in the pipe. At the end of the paper the authors give an estimate of the computing time for factoring a 100-digit number, viz. about two weeks. Extrapolation shows that a 144-digit number can be factored in about a year.
Reviewer: J.van der Linden

MSC:

11-04 Software, source code, etc. for problems pertaining to number theory
11A41 Primes
68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI Link