Question

Trace Algorithm 4 when it is given m = 5 , n = 11 , and b = 3 as input. That is, show all the steps Algorithm 4 uses to find 3 mod 5 .

Short answer

The value is$3^{11}\mathrm{mod}5=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 = 11 , m = 5 and b = 3.

$3^{11}\mathrm{mod}5=\mathrm{mpower}(3,11,5)$

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

Determine mpower (3,5,5).

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

Determine mpower (3,2,5).

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

Simplify further.

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

Evaluate the found expression for mpower (3,5,5).

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

Simplify further.

$\begin{array}{r}\mathrm{mpower}(3,5,5)=[4\cdot 3]mod5\\ =12mod5\\ =2\end{array}$

Evaluate the found expression for mpower (3,11,5).

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

Simplify further.

$\begin{array}{r}{3}^{11}mod5=[4mod5\cdot 3]mod5\\ =[4\cdot 3]mod5\\ =12mod5\\ =2\end{array}$

Therefore, the value is$3^{11}\mathrm{mod}5=2$ .