Skip to main content
Article
Bound Optimization for Parallel Quadratic Sieving Using Large Prime Variations
Undergraduate Honor's Thesis, Washington & Lee University (2007)
  • Andrew G. West, Washington and Lee University
Abstract

The Quadratic Sieve (QS) factorization algorithm is a powerful means to perform prime decompositions that combines number theory, linear algebra, and brute processing power. Created by Carl Pomerance in 1985, it is the second fastest general purpose factorization method as of this writing, behind only the Number Field Sieve.

We describe an efficient QS implementation which is accessible to an undergraduate audience. The majority of papers on this topic rely on complex mathematical notation as their primary means of explanation. Instead, we attempt to combine math, discussion, and examples to promote understanding. Additionally, few authors ever present implementation level detail. With the significant time and memory requirements of the extremely iterative algorithm, even minor optimizations can result in large runtime improvements and these are described. Discussion covers both sequential and parallel implementations, as the latter is required to factor numbers of a signficant magnitude.

We use our implementation to optimize the selection of prime bounds which are critical to QS runtime. Analysis begins with basic QS, a simplified version of the more powerful PQS (QS w/Large Prime Variations), which is later given attention. Both theory and concrete statistics guide us in determining how variable selection can be used to minimize runtimes. Given that data, we attempt to extrapolate bound selection for larger integers, whose size makes them inappropriate for casual experimentation. We find that predicting ideal bounds for basic QS can be done with some degree of accuracy, however, PQS behaves more erratically making extrapolation difficult.

Disciplines
Publication Date
May 1, 2007
Citation Information
Bound Optimization for Parallel Quadratic Sieving Using Large Prime Variations. Andrew G. West. Undergraduate Honor's Thesis, Washington & Lee University. May 2007.