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:
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.)