Motivation

In contrast to finding and multiplying of large prime numbers, no efficient classical algorithm for the factorisation of large number is known. An algorithm is called efficient if its execution time i.e. the number of elementary operations is assymtotically polynomial in the length of its input measured in bits. The best known (or at least published) classical algorithm (the quadratic sieve) needs $O\left(\exp\left(({64 \over 9})^{1/3} N^{1/3}(\ln N)^{2/3}\right)\right)$ operations for factoring a binary number of $N$ bits [7] i.e. scales exponentially with the input size.

The multiplication of large prime numbers is therefore a one-way function i.e. a function which can easily be evaluated in one direction, while its inversion is practically impossible. One-way functions play a major roll in cryptography and are essential to public key cryptosystems where the key for encoding is public and only the key for decoding remains secret.

In 1978, Rivest, Shamir and Adleman developed a cryptographic algorithm based on the one-way character of multiplying two large (typically above 100 decimal digits) prime numbers. The RSA method (named after the initials of their inventors) became the most popular public key system and is implemented in many communication programs (e.g. Netscape, PGP, etc.).

While it is generally believed (although not formally proved) that efficient prime factorisation on a classical computer is impossible, an efficient algorithm for quantum computers has been proposed in 1994 by P.W. Shor [6].