Keywords: factorization, prime numbers, number theory
Prerequisites: 01018: Discrete Mathematics 2
The security of the RSA cryptosystem depends on the hardness of the integer factoring problem. In general this is a hard problem for which no fast algorithms are known. More precisely, given a natural number \(N \le 10^n\) there currently does not exist an algorithm that would for any such \(N\) finds all its prime factors in time polynomial in n.
While naïve algorithms such as finding prime factors of n by trial and error, have exponential running time in \(n\), there also exist factoring algorithms that have so-called subexponential running time in \(n\). One example of such an integer factoring algorithm is the quadratic sieve.
The currently fastest integer factoring algorithm is the famous number field sieve. The name of this algorithm comes from number fields: finite dimensional algebraic extension fields of \(\mathbb{Q}\). In this project you will learn about number fields and several rings contained in them as well as their relation to the number field sieve.