Exercise 2.4.2 (Fast exponentiation)

Proof.

a)

The algorithm of fast exponentiation described page 77 gives the following intermediate results $$\begin{array}{cccc}\hfill a\hfill & \hfill n\hfill & \hfill n\mathit{mod}2\hfill & \hfill \mathrm{result}\hfill \\ & & & \\ \hfill 2\hfill & \hfill 45\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 4\hfill & \hfill 22\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 16\hfill & \hfill 11\hfill & \hfill 1\hfill & \hfill 32\hfill \\ \hfill 74\hfill & \hfill 5\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 16\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 74\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 57\hfill \end{array}$$

where, at the beginning

$$a\leftarrow 2,\mathrm{result}\leftarrow 1,$$

and at each step of the loop,

$$\begin{array}{llll}\hfill & \mathrm{result}\leftarrow a\cdot \mathrm{result}\mathit{mod}p(\text{if }n\text{ mod }2=0),& \hfill & \\ \hfill & a\leftarrow (a\cdot a)\mathit{mod}p& \hfill & \\ \hfill & n\leftarrow \lfloor n∕2\rfloor & \hfill & \\ \hfill & \text{if }n=0:\mathrm{stop}.& \hfill & \end{array}$$

At the end, $\mathrm{result}=a^n(\mathit{mod}p)$.

Python:

     def powermod(a,n,p):
         result = 1
         while n!= 0:
             if n % 2 != 0:
                 result = (a * result) % p
             a = (a * a) % p
             n = n // 2
         return result

b)

By part (a), we obtain $$2^{45}\equiv 57\not\equiv \pm 1(\mathit{mod}91).$$

If $n=91$ was prime, we would obtain $2^{(n-1)∕2}\equiv \pm 1(\mathit{mod}n)$. Therefore $91$ is composite