-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$
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}

| improve this answer | |
$\endgroup$
  • $\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.