Factoring integers, Producing primes and the RSA cryptosystem

Francesco Pappalardi

This will be an introductory talk. After having outlined some of the highlights of the “history of integer factorisation”, we will explain how to use the hardness of factoring integers to design the RSA public key cryptosystem.

The implementation of such a cryptosystem is the motivation for primality testing. We will review classical Monte Carlo algorithms and finally we will describe the recent AKS primality algorithm that allows to prove primality in polynomial time.