Powers modulo a prime

The sequence

$$a\quad a^2\quad a^3\dots\quad\hbox{mod }p$$

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 $432^{678}$ mod 987. The basic trick is to start with a number and keep squaring:

$$432^2=186624{\equiv}81\quad432^4{\equiv}81^2{\equiv}639\quad432^8{\equiv} 639^2{\equiv}690\dots432^{512}{\equiv}858$$

Since $678=512+128+32+4+2$,

$$432^{678}{\equiv}(81)(639)\dots(858) {\equiv}204\qquad\hbox{(I hope!)}$$

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 (see Knuth, volume 2).

Let us look at the sequence of powers of 2 mod 11:

$$2 4 8 5 10 9 7 3 6 1$$

Each number from 1 to 10 appears in the sequence.

Theorem 5   Let $p$ be a prime. There is an $a$ such that for every $1\le b\le p-1$, there is $1\le x\le p-1$ such that ${a^x}\equiv{b}\hbox{ (mod }{p})$.

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.

The proof of Theorem 5 is long, and we will give it in section 2.5. For now, we want to look at some of its consequences.

Corollary 6   Let $a$ be as in Theorem 5. Then ${a^{p-1}}\equiv{1}\hbox{ (mod }{p})$.

Proof: We know that $a^d{\equiv}1$ for some $1\le d\le p-1$. If $d<p-1$, the sequence of powers of $a$ would start repeating before we got all the numbers: $a^{d+1}{\equiv} a$, $a^{d+2}{\equiv} a^2$, etc. height 8pt width 4pt

Corollary 7   For any $b\not{\equiv}0$, ${b^{p-1}}\equiv{1}\hbox{ (mod }{p})$.

Proof: Let $a$ be as in Theorem 5. Using Corollary 6

$$b^{p-1} {\equiv} a^{x(p-1)}{\equiv}\left(a^{p-1}\right)^x{\equiv}1\quad\mbox{\vrule height 8pt width 4pt}$$

Corollary 8   If ${x}\equiv{y}\hbox{ (mod }{(p-1)})$, then ${b^x}\equiv{b^y}\hbox{ (mod }{p})$

Proof: For some integer $r$, $y=r(p-1)+x$ and by Corollary 7

$$b^y{\equiv}{\left(b^{p-1}\right)^rb^x}\equiv{b^x}\hbox{ (mod }{p})\quad\mbox{\vrule height 8pt width 4pt}$$

Lemma 9   Let $b\not{\equiv}0$, $d$ the smallest positive number such that $b^d{\equiv}1$. Then for any $e>0$ with $b^e {\equiv} 1$ $d$ divides $e$ evenly. In particular, by Corollary 7, $d$ divides $p-1$ evenly.

Proof: If $d$ does not divide $e$, then $e=dr+s$ for some $0<s<d$, but

$$b^s{\equiv} b^{e}\left(b^d\right)% ^{-r}{\equiv}1$$

would contradict the definition of $d$. height 8pt width 4pt