On the Quadratic Sieve

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Stephani Lee Garrett (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/
Paul Duvall

Abstract: Factoring large integers has long been a subject that has interested mathematicians. And although this interest has been recently increased because of the large usage of cryptography, the thought of factoring integers that are hundreds of digits in length has always been appealing. However it was not until the 1980's that this even seemed fathomable; in fact in 1970 it was extremely difficult to factor a 20-digit number. Then in 1990 the Quadratic Sieve factored a record 116-digit number. While the Quadratic Sieve is not the most recent development in factoring, it is more efficient for factoring numbers below 100-digits than the Number Field Sieve. This paper will discuss the methodology behind the Quadratic Sieve, beginning in its roots in Fermat and Kraitchik's factoring methods. Furthermore our objective is to fully describe the Quadratic Sieve with the goal that the reader could implement a reproduction of the sieve for small numbers.

Additional Information

Language: English
Date: 2008
Quadratic Sieve, Factor, Smooth Numbers, Sieve, Multiple Polynomial Quadratic Sieve, Factorization Methods
Number theory.
Factorization (Mathematics)

Email this document to