Question

Trace Algorithm 4 when it is given m = 7 , n = 10 , and b = 2 as input. That is, show all the steps Algorithm 4 uses to find${\mathbf{2}}^{\mathbf{10}}$mod 7 .

Short answer

The value is$2^{10}\mathrm{mod}7=2$ .

Step-by-step solution

Recursive Definition

From the recursive definition,

$\mathbf{mpower}\mathbf{}\mathbf{(}\mathbf{b}\mathbf{,}\mathbf{n}\mathbf{,}\mathbf{m}\mathbf{)}\mathbf{=}\{\begin{array}{l}1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}n=0\\ \mathrm{mpower}(b,n/2,m{)}^{2}modm\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}n\text{even}\\ \left[\mathrm{mpower}(b,\lfloor n/2\rfloor ,m{)}^{2}modm\cdot bmodm\right]modm\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{otherwise}\end{array}$

Determine the recursive

Evaluate the recursive definition at n = 10 , m =7 and b = 2.

$\begin{array}{r}{2}^{10}mod7=\mathrm{mpower}(2,10,7)\\ =\left[\mathrm{mpower}(2,\lfloor 10/2\rfloor ,7{)}^{2}mod7\right]\\ =\left[\mathrm{mpower}(2,5,7{)}^{2}mod7\right]\\ ={\left(\left[\mathrm{mpower}(2,\lfloor 5/2\rfloor ,7{)}^{2}mod7\cdot 2mod7\right]mod7\right)}^{2}mod7\end{array}$

Simplify further.

$2^{10}mod7={\left(\left[\mathrm{mpower}(2,2,7{)}^{2}mod7\cdot 2\right]mod7\right)}^{2}mod7$

Determine (2,2,7).

$\begin{array}{r}\mathrm{mpower}(2,2,7)=\left[\mathrm{mpower}(2,\lfloor 2/2\rfloor ,7{)}^{2}mod7\right]\\ =\left[\mathrm{mpower}(2,1,7{)}^{2}mod7\right]\\ ={\left(\left[\mathrm{mpower}(2,\lfloor 1/2\rfloor ,7{)}^{2}mod7\cdot 2mod7\right]mod7\right)}^{2}mod7\\ ={\left(\left[\mathrm{mpower}(2,0,7{)}^{2}mod7\cdot 2\right]mod7\right)}^{2}mod7\end{array}$

Simplify further.

$\begin{array}{r}\mathrm{mpower}(2,2,7)={\left(\left[1^{2}mod7\cdot 2\right]mod7\right)}^{2}mod7\\ =\left(\right[1\cdot 2]mod7{)}^{2}mod7\\ =(2mod7{)}^{2}mod7\\ =2^{2}mod7\end{array}$

Simplify further.

$\begin{array}{r}\mathrm{mpower}(2,2,7)=4mod7\\ =4\end{array}$

Evaluate the found expression for (2,10,7).

$\begin{array}{r}{2}^{10}mod7=\mathrm{mpower}(2,10,7)\\ =\mathrm{mpower}(2,\lfloor 10/2\rfloor ,7{)}^{2}mod7\\ =\left[\mathrm{mpower}(2,5,7{)}^{2}mod7\right]\\ ={\left(\left[\mathrm{mpower}(2,\lfloor 5/2\rfloor ,7{)}^{2}mod7\cdot 2mod7\right]mod7\right)}^{2}mod7\end{array}$

Simplify further.

$\begin{array}{r}{2}^{10}mod7={\left(\left[\mathrm{moower}(2,2,7{)}^{2}mod7\cdot 2\right]mod7\right)}^{2}mod7\\ ={\left(\left[4^{2}mod7\cdot 2\right]mod7\right)}^{2}mod7\\ =\left(\right[16mod7\cdot 2]mod7{)}^{2}mod7\\ =\left(\right[2\cdot 2]mod7{)}^{2}mod7\end{array}$

Simplify further.

$\begin{array}{r}{2}^{10}mod7=(4mod7{)}^{2}mod7\\ =4^{2}mod7\\ =16mod7\\ =2\end{array}$

Therefore, the value is $2^{10}\mathrm{mod}7=2$.