Introduction

All sources for this blog post can be found in the Github repository about large primes. The most recent version of the sources may only be found in the Github repository.

It has been a long time since I found the energy to write a new blog post. In this article, I am going to dig into a interesting area of cryptography: The task to find large prime numbers. We hopefully are all familiar with the concept of prime numbers. Prime numbers are integers \(p\) which are dividable only by \(p\) itself and \(1\). But why is it necessary to find large prime numbers in the area of cryptography?

One of the first asymmetric cryptosystems invented was RSA (1977). As all public key algorithms, the security of RSA depends on the existence of a one-way function.

In the case of RSA, the one-way function is built on top of the integer factorization problem: Given two prime numbers \(p,q\in \mathbb{N}\), it is straightforward to calculate \(n=p \cdot q\), but it is computationally infeasible to reverse this multiplication by finding the factors \(p\) and \(q\) given the product \(n\). Even when the primes \(p\) and \(q\) are …

Continue reading