Honors Thesis

Bound Optimization for Parallel Quadratic Sieving using Large Prime Variations

Andrew West '07

(:abstract:) The Quadratic Sieve (QS) factorization algorithm is an efficient means of integer factorization when deployed in an optimized manner across a parallel environment. To demonstrate this, one first must understand when it is appropriate to use such an algorithm and how it compares to other factorization methods.

From there, the mathematical foundations of the method must be established with discussion concerning the limitations of trial division, Fermat, and congruence of squares. This basis permits an explanation of Dixon's factorization algorithm, a slightly altered form of the Quadratic Sieve. An explanation of quadratic residues and their role in moving from Dixon to a true Quadratic Sieve will conclude the abstract mathematical discussion.

Next, implementation concerns will be addressed. Starting in a sequential environment every type-choice, coding anamoly, and method will be intimately reviewed with the goal of creating the most efficient QS. Following that, the same discussion will take place with regards to a parallel environment. Timings and associated graphs will be used to support these claims.

This paper will conclude by detailing the significance of integer factorization to computer security. Quicker factorization methods will be introduced along with the possible benefit this research could be of to them. Finally, mention will be made of the possible shortcomings of this work and the hardware on which it was performed. (:abstractend:)

<< | Main List | Andrew White >>