Use the binary exponentiation algorithm to compute....

[Math100]

Homework Statement

Use the binary exponentiation algorithm to compute both $19^{53}\pmod {503}$ and $141^{47}\pmod {1537}$.

Relevant Equations

None.

First, consider $19^{53}\pmod {503}$.
Then $53=(110101)_{2}=2^{5}+2^{4}+2^{2}+1=32+16+4+1$.
Note that
\begin{align*}
19^{2}\equiv 361\pmod {503}\\
19^{4}\equiv 44\pmod {503}\\
19^{8}\equiv 427\pmod {503}\\
19^{16}\equiv 243\pmod {503}\\
19^{32}\equiv 198\pmod {503}.\\
\end{align*}
Thus $19^{53}\equiv (19^{32}\cdot 19^{16}\cdot 19^{4}\cdot 19)\pmod {503}\equiv (198\cdot 243\cdot 44\cdot 19)\pmod {503}$.
Therefore, $19^{53}\equiv 406\pmod {503}$.
Next, consider $141^{47}\pmod {1537}$.
Then $47=(101111)_{2}=2^{5}+2^{3}+2^{2}+2+1=32+8+4+2+1$.
Note that
\begin{align*}
141^{2}\equiv 1437\pmod {1537}\\
141^{4}\equiv 778\pmod {1537}\\
141^{8}\equiv 1243\pmod {1537}\\
141^{16}\equiv 364\pmod {1537}\\
141^{32}\equiv 314\pmod {1537}\\
\end{align*}
Thus $141^{47}\equiv (141^{32}\cdot 141^{8}\cdot 141^{4}\cdot 141^{2}\cdot 141)\pmod {1537}\equiv (314\cdot 1243\cdot 778\cdot 1437\cdot 141)\pmod {1537}$.
Therefore, $141^{47}\equiv 658\pmod {1537}$.

 

[fresh_42]

I checked the first one in detail and both results. Everything is fine.

Only a remark on the second one: you can alternatively calculate
$$
\dfrac{{141}^{32}\cdot {141}^{16}}{141} = {141}^{32}\cdot {141}^{16}\cdot 1428 \pmod {1537}
$$
but I had the computer calculate $141^{-1} =1428 \pmod {1537}$ so I do not know whether this is really an improvement. However, it is something to keep in mind for modules smaller than $1537$.