C# GNFS

C# .NET implementation of the general number field sieve for factoring very large semi-prime numbers, which are used by the RSA public key encryption algorithm. The general number field sieve is an involved process, consisting of many steps: a polynomial creation, testing and selection process, finding 'relations' who's algebraic and rational norms are smooth with respect to an algebraic and rational factor base, the creation, and solving of a (very) large (0,1)-matrix to find sets of relations where the product of all the norms in that set are a perfect square number, finding the square roots of polynomials over a finite field, the Chinese remainder theorem and finally the testing of several found candidates for a non-trivial difference of squares.

Did you understood all that? Good. Because it's * just * that easy, folks!   /s

Screenshots

Literature & Publications

Below is some literature on the subject of General Number Field Sieves that helped guide me during the construction of this project. Most of the code was written after reading Per Leslie Jensen's paper. However, the final step, finding the square root of a polynomial over a finite field (or called simply the 'square root step') was the most challenging step because it required an understanding of abstract algebra, and Per Leslie Jensen's paper was almost completely void of any details pertaining to this step. I used Matthew E. Briggs's paper to help guide me in writing the code for the final step.

• Factoring integers with the number field sieve - J.P. Buhler, H.W Lenstra, Jr., and Carl Pomerance
• An Introduction to the General Number Field Sieve - Matthew E. Briggs
• Integer Factorization - Master Thesis - Per Leslie Jensen
• The development of the number field sieve - H. W. Lenstra, Arjen K. Lenstra, Hendrik W. Lenstra
• A General Number Field Sieve Implementaion - DJ Bernstein & Lenstra
• The Multiple Polynomial Quadradic Sieve - R.D. Silverman
• The Number Field Sieve - C. Pomerance