Powers in Modular Arithmetic

Both the Fiat-Shamir Zero-Knowledge Protocol and the RSA public-key cryptosystem involve computing powers in modular arithmetic. We will start out with a simple example, the powers of 3 modulo 19. Instead of entering things like 3¹⁷ on our calculator, we shall build up slowly, each time multiplying the previous result by 3:

$$\begin{split} 3^0 &\equiv 1 \pmod{19}\\ 3^1 &\equiv 3 \p... ...}\\ 3^9 &\equiv 3\cdot 6 =18 \equiv -1 \pmod{19} \end{split}$$ (8.1)

We don't really have to go any further, because the remaining sequence of powers will be exactly the negative the sequence we have encountered so far, thanks to $3^9\equiv -1\pmod{19}$. That is the full sequence of powers is

$$1,\;3,\;9,\;8,\;5,\;15,\;7,\;2,\;6,\; -1,\;-3,\;-9,\;-8,\;-5,\;-15,\;-7,\;-2,\;-6$$

or equivalently

$$1,\;3,\;9,\;8,\;5,\;15,\;7,\;2,\;6,\; 18,\;16,\;10,\;11,\;14,\; 4,\;12,\;17,\;13$$

using modular equivalence.

Our example, shows a few things that are true in general. First, it is very easy to compute modular powers, since our numbers can always be reduced to less than the modulus m. Secondly, the actual values tend to wander around the numbers from 1 to m-1, but they always eventually repeat. One thing we wish to learn here is how long is before the powers repeat. Since the 0-th power is always 1, that comes down to determining the smallest positive integer k such that the k-th power is congruent to 1. Then the cycle of powers will repeat every k powers.

To be a little more general now, let m be the modulus and let a be the number that we are raising to a power. So we are considering the powers $a^k \pmod m$. If $a^k \equiv 1 \pmod m$, then a^k-1 is a multiple of m. Suppose a^k-1=lm for some integer l.

That says one very important thing about the relation between a and m: they have to be relatively prime. If not, there would an integer d>1 that divides both a and m. That is the same as saying $a\equiv m\equiv 0 \pmod d$. Then, since a^k-1=lm, we conclude

$$1= lm-a^k \equiv 0-0 \pmod d$$

That is clearly impossible if d>1. Our conclusion is that a and m must have been relatively prime all along. This situation need a little exploration.