Factorization

Factorization

Submitted by Detlev Conrad … on Sun, 10/21/2012 - 17:07

Large number factorization was the topic of my BSc thesis, which is an abstract pure maths topic with a very practical application.

It is easy to multiply two large numbers with each other, however difficult to factorize a large number into its components.

This basic problem is the cornerstone of secure modern communication which employs public key cryptography, vital for tasks such as online banking and online shopping or just simple secure communication. Techniques to factorized large number have improved over time, however even the fastest method, the number field sieve cannot, at the moment, be employed to factorize a large product of two primes in a reasonable amount of time.

My specific focus lay on the predecessor of the number field sieve, which is the slower quadratic sieve including a (cumbersome) implementation in C++ available on sourceforge:

https://sourceforge.net/projects/quadraticsieve/