Fermat's little theorem was used by Rivest, Shamir, and Adelman to design a fascinating encryption algorithm, in which you can tell anyone you like how the encryption works, although this knowledge is not sufficient to be able to decrypt; decryption is only possible for the chosen few who have extra information.

Let's see how this works on a simple example.

Let's assume that the text we want to encrypt is:

WHATEVER

First we have to translate this text into numbers. To do this, we shall use a hash code, which replaces every character by an integer. (We'll see more examples on the next page.) For the word whatever this gives:

23 8 1 20 5 22 5 18

To encrypt this text, we will replace every number x by another number y, according to a simple rule.

The key to this encryption rule is given by two numbers n and r. The number n is chosen in a very particular way:

n is the product of two primes p and q.

Suppose we choose n = 29 * 37 = 1073. Let's take r = 25.

To encrypt x we just compute:

To decrypt y we need a decryption key, which takes the form of a number s. In this particular case, with this choice of n and r, the choice s = 121 is an appropriate decryption key.

The decryption then works via a simple formula, analogous to the encryption: we compute

and this gives us x back again! (We'll come back below to why this happens.)