1. State of the art

1.1 Ron Rivest, Adi Shamir, Leonard Adleman, integer factorization

The RSA encryption algorithm was invented by Ron Rivest, Adi Shamir and Leonard Adleman in 1977. It was one of the first "public key" encryption algorithms, meaning that encrypting a message does not require the sender to share a secret with the recipient. Since then, it has become one of the world's most widely used encryption and authentication algorithms: it is used in the HTTPS protocol, which secures websites, and in PGP, the message encryption software.

When Alice wants to send a secret message m to Bob, this encryption algorithm works as follows:

• Bob chooses two very large primes p and q, and calculates their product n = p·q. He also chooses...