Question

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

Short answer

${11}^{644}mod645=1$

Step-by-step solution

Step 1

Given

${11}^{644}mod645$

Let us first determine the binary expansion of 644.

$664=(1010000100{)}_2$

$a_1$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 xis set to 1 and power is set to 11 mod 645

role="math" localid="1668518827174" $$\begin{gathered} x=1 \\ \text{Power}=11\mathbf{mod}645=11 \end{gathered}$$

Step 2

When $a_1=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$since $a_0=0$

$x=1$

role="math" localid="1668518978529" $\text{power}={11}^{2}mod645=121mod645=121$

role="math" localid="1668519468747" width="134" height="68">i=1Sincea1=0:x=1

$$\begin{gathered} x=1.451=451 \\ \text{power}={451}^{2}mod645=203401mod645=226 \\ \mathbf{i}=\mathbf{3}{\text{Sincea}}_3=0 \\ x=451 \\ \text{power}={451}^{2}mod645=203401mod645=226 \\ \mathbf{i}=\mathbf{3}{\text{Sincea}}_3=0 \\ x=451 \\ \text{power}={226}^{2}mod645=51076mod645=121 \\ \mathbf{i}=\mathbf{4}{\text{Sincea}}_4=0 \\ \begin{array}{r}x=451\\ \\ \text{power}={121}^{2}mod645=14641mod645=451\end{array} \end{gathered}$$

$\mathbf{i}=\mathbf{6}{\text{Sincea}}_6=0$

$x=451$

$\text{power}={226}^{2}mod645=51076mod645=121$

Step 3

$\begin{array}{r}\mathbf{i}=7{\text{Sincea}}_7=1:\\ \\ x=451\cdot 121mod645=54571mod645=391\\ \\ \text{power}={121}^{2}mod645=14641mod645=451\\ \\ \mathbf{i}=\mathbf{8}{\text{Sincea}}_8=0\\ \\ x=391\\ \\ \text{power}={451}^{2}mod645=203401mod645=226\\ \\ \mathbf{i}=9{\text{sincea}}_9=1:\\ \\ x=391\cdot 226mod645=88366mod645=1\\ \\ \text{power}={226}^{2}mod645=203401mod645=226\\ \\ \text{return}x=1\end{array}$