has many applications in cryptography. Before looking at theoretical properties, the example below (done using a pocket calculator) should make clear that it is practical to compute these numbers, even when many digits are involved.
Suppose we want to compute mod 987. The basic trick is to start with a number and keep squaring:
Since 678=512+128+32+4+2,
Calculations with exponents involve not-too-many multiplications. If the numbers have several hundred digits, however, it is necessary to design special subroutines to do the multiplications [Knu81].
Let us look at the sequence of powers of 2 mod 11:
Each number from 1 to 10 appears in the sequence.
It is not always the case that a=2. The powers of 2 mod 7 are 2, 4, 1 after which the sequence repeats and we never get 3, 5, or 6.
Let's look at some of the consequences of Theorem 5.