-3
$\begingroup$

Evaluate $17^{93} \mod 23$

\begin{align}e &= 93\\ &= 1 × 2^6 + 0 × 2^5 + 1 × 2^4+ 1 × 2^3 + 1 × 2^2 + 0 × 2^1 + 1 × 2^0\\ &= |\ 1011101\ |_2 \end{align} Then we have: \begin{align}17^{93} \mod 23 &= (((((((17^1 )^2 17^0 )^2 17^1 )^2 17^1 )^2 17^1 )^2 17^0 )^2 17^1\\ &= (((17^4 17)^2 17)^2 17)^4 17 \text{ $\leftarrow$ step 3}\\ &= 21 \end{align}

How do we go from step 3 to final answer? What are the theorems used?

$\endgroup$
2
1
$\begingroup$

This is just a modular multiplication : \begin{align}17^{93} \mod 23 &= (((((((17^1 )^2 17^0 )^2 17^1 )^2 17^1 )^2 17^1 )^2 17^0 )^2 17^1\\ &= (((((17^2)^2 17)^2 17)^2 17)^2)^2 17 \text{ $\leftarrow$ step 3}\\ &= (((((289 \bmod\ 23)^2 17)^2 17)^2 17)^2)^2 17\\ &= ((((13^2 17)^2 17)^2 17)^2)^2 17\\ &= (((((169 \bmod\ 23) 17)^2 17)^2 17)^2)^2 17\\ &= ((((8 \times 17)^2 17)^2 17)^2)^2 17\\ &= ((((136 \bmod 23)^2 17)^2 17)^2)^2 17\\ &= (((21^2 17)^2 17)^2)^2 17\\ &= ((((441\ \bmod\ 23) 17)^2 17)^2)^2 17\\ &= (((4 \times 17)^2 17)^2)^2 17\\ &= etc..\\ &= 21 \end{align}

$\endgroup$
6
  • $\begingroup$ 17^93 = 17^5 x (17^22)^4 then (17^22)^4 mod(23) = 1 (Fermat's theorem) then 17^5 mod 23 = 21 $\endgroup$
    – user11
    May 11 '16 at 6:16
  • $\begingroup$ @user11 yes, but when you use an algorithm to compute the answer, you cannot use the Fermat theorem in such a way. $\endgroup$
    – Biv
    May 11 '16 at 8:11
  • $\begingroup$ You mean the method will no longer be fast exponentiation method? $\endgroup$
    – user11
    May 11 '16 at 8:18
  • $\begingroup$ @user11 exactly. $\endgroup$
    – Biv
    May 11 '16 at 8:20
  • $\begingroup$ Alright. Applying fermat's theorem seems to be fast in this problem? $\endgroup$
    – user11
    May 11 '16 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.