Andrew West '07 Bound Optimation for Parallel Quadratic Sieving using Large Prime Variations
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 genera l purpose factorization method as of this writing, behind only the Number Field Sieve. Our purpose is two-fold:
First, 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 significant magnitude.
Second, we use our implementation to optimize the selection of variables (prime bounds) 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 large integers, whose size makes them inappropriate for casual experimentation. We find that predicting ideal bounds for basic Q S can be done with some degree of accuracy, however, PQS behaves more erratically making extrapolation difficult. More work could confirm these claims, further promoting the assertion of several authors that bound selection is "as much art as science.'"