Rasmus Persson: Integer Factorization

Abstract.

Integer factorization is crucial for understanding the security of the most widely known cryptosystems. These systems rely on the difficulty of factoring large integers. Therefore, it is important to understand the current methods for factoring integers, in order to know if the currently used encryption methods are still secure. In the first part of this thesis we present the idea of public key cryptography. In the second part we review some necessary theoretical background from abstract algebra. In the third and main part we present a selection of four methods for factoring integers. The simplest one is Pollard’s \(p-1\) algorithm. It works for some numbers, and highlights that for an integer \(N = pq\) to be difficult to factor, we need to ensure that \(p-1\) or \(q-1\) does not factor into small primes. The other algorithms are based on trying to find a pair of numbers \(a\) and \(b\) so that \(N\) divides \(a^2 - b^2\), but does not divide \(a-b\) or \(a+b\). If we find such a pair, we can factor \(N\) by finding \(\gcd(a - b, N)\). The most sophisticated algorithm that we discuss is the number field sieve. It is currently the fastest method for factoring integers larger than \(2^{450}\). The details of the number field sieve are very complicated, and we only outline the main ideas behind this algorithm.