Question

Use Algorithm 5 to find ${123}^{1001}mod101$

Short answer

${123}^{1001}mod101=22$

Step-by-step solution

Step 1

Given

${123}^{1001}mod101$

Let us first determine the binary expansion of 1001.

$1001={\left(\begin{array}{l}11\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}11101001\end{array}\right)}_2$

$a_1$then represents the ith digit in the binary expansion of 1001

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

Initially x is set to 1 and power is set to 123 mod 101

role="math" localid="1668515145493" $$\begin{gathered} x=1 \\ \text{power}=123mod101=22 \end{gathered}$$

Step 2

When $a_i=1\text{then}x$is first multiplied by the power and reduced modulo 101

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

localid="1668515953434" $$\begin{gathered} \mathbf{i}=\mathbf{0}{\text{Sincea}}_0=1 \\ x=1\cdot 22mod101=22mod101=22 \\ \text{power}={22}^{2}mod101=484mod101=80 \\ \mathbf{i}=\mathbf{1}{\text{Sincea}}_1=1: \\ x=22 \\ \text{power}={80}^{2}mod101=6400mod101=37 \\ \mathbf{i}=\mathbf{2}\mathrm{Sin}ce{a}_2=0: \\ x=22 \\ \text{power}={37}^{2}mod101=139mod101=56 \\ \mathbf{i}=\mathbf{3}{\text{Sincea}}_3=1: \\ x=22\cdot 56mod101=1232mod101=20 \\ \text{power}={56}^{2}mod101=3136mod101=5 \\ \mathbf{i}=\mathbf{4}{\text{Sincea}}_4=0 \\ x=20 \\ \text{power}=5^{2}mod101=25mod101=25 \\ \mathbf{i}=\mathbf{5}{\text{Sincea}}_5=1: \\ x=20\cdot 25mod101=500mod101=96 \\ \text{power}={25}^{2}mod101=100mod101=19 \\ \mathbf{i}=\mathbf{6}{\mathrm{sincea}}_6=1: \\ x=96\cdot 19mod101=1824mod101=6 \\ \text{power}={19}^{2}mod101=361mod101=58 \end{gathered}$$

Step 3

$$\begin{gathered} \mathbf{i}=\mathbf{7}{\text{Sincea}}_7=1\text{:} \\ x=6\cdot 58mod101=348mod101=45 \\ \text{power}={58}^{2}mod101=3364mod101=31 \\ \mathbf{i}=\mathbf{8}{\mathrm{Sincea}}_8=1: \\ x=45\cdot 31mod101=1395mod101=82 \\ \text{power}={31}^{2}mod101=961mod101=52 \\ \mathbf{i}=\mathbf{9}{\mathrm{sincea}}_0=1: \\ x=9.9mod99=81mod99=81 \\ \text{power}=9^{2}mod99=81mod99=81 \\ \mathbf{i}=\mathbf{10}{\text{Sincea}}_{10}=1: \\ x=82\cdot 52mod101=4264mod101=22 \\ \text{power}={52}^{2}mod101=2704mod101=78 \\ \text{return}x=22 \end{gathered}$$