Prime numbers are essential in cryptography. Many cryptographic primitives (RSA encryption, ElGamal, digital signatures…) rely on finding and using large prime numbers (in the range of 256-2048 bits long). But, why are prime numbers important for cryptography? And, how can we check whether such large numbers are prime?

In this talk, I will present different techniques to assure primality, such as probabilistic algorithms (that assure with very high probability that the number is prime) and the celebrated AKS algorithm (which is the first known deterministic algorithm for primality checking running in polynomial time). These algorithms are efficient enough to be used in actual cryptographic applications.

Additionally, I will talk about the largest prime numbers known by humanity and how we know they are prime (note that the mentioned algorithms cannot be used to assure primality of these staggering numbers and dedicated algorithms must be employed).