Question

Use Algorithm 5 to find$7^{644}mod645$

Short answer

$7^{644}mod645$= 436

Step-by-step solution

Step 1

Given

$7^{644}mod645$

Let us first determine the binary expansion of 644.

$664=(1010000100{)}_2$

$a_2$then represents the ith digit in the binary expansion of 644

$\begin{array}{r}{a}_2=a_7=a_9=1\\ \\ a_0=a_1=a_3=a_4=a_5=a_6=a_8=0\end{array}$

Initially x is set to 1 and power is set to$7mod645$

$x=1$

$\text{power}=7mod645$

Step 2

When $a_i=1$then x is first multiplied by the power and reduced modulo 645

Then on each iteration the power is multiplied by itself and reduced modulo 645.

$\mathrm{i}=0\text{since}{a}_0=0$

$x=1$

$$\begin{gathered} \text{power}=7^{2}mod645=49mod645=49 \\ \begin{array}{r}\mathbf{i}=\mathbf{1}{\text{Sincea}}_1=0:\\ \\ x=1\\ \\ \text{power}={49}^{2}mod645=2401mod645=466\\ \\ x=1.466=466\\ \\ \text{power}={466}^{2}mod645=217156mod645=436\\ \\ \mathbf{i}=\mathbf{3}{\text{Sincea}}_3=0\\ \\ x=466\\ \\ \text{power}={436}^{2}mod645=190096mod645=466\\ \\ \mathbf{i}=\mathbf{4}{\text{Sincea}}_4=0\\ \\ x=466\\ \\ \text{power}={466}^{2}mod645=217156mod645=436\\ \\ \mathbf{i}={\text{Since}}_5=0\\ \\ x=466\\ \\ \text{power}={436}^{2}mod645=190096mod645=466\\ \\ \mathbf{i}=\mathbf{6}{\text{Since}}_6=0\\ \end{array} \end{gathered}$$

$$\begin{gathered} x=466 \\ \text{power}={466}^{2}mod645=217156mod645=436 \end{gathered}$$

$\begin{array}{r}\mathbf{i}=\mathbf{6}{\text{Sincea}}_6=0\\ \\ x=466\\ \\ \text{power}={466}^{2}mod645=217156mod645=436\end{array}$

Step 3

$\begin{array}{r}\mathbf{i}=7{\text{Sincea}}_7=1:\\ \\ x=466\cdot 436mod645=203176mod645=1\\ \\ \text{power}={436}^{2}mod645=190096mod645=466\\ \\ \mathbf{i}=8{\text{Sincea}}_8=0:\\ \\ x=1\\ \\ \text{power}={466}^{2}mod645=217156mod645=436\\ \\ \mathbf{i}=9{\text{sincea}}_9=1:\\ \\ x=1\cdot 436mod645=436mod645=436\\ \\ \text{power}={436}^{2}mod645=190096mod645=466\\ \\ \text{return}x=436\end{array}$