binära tal

Hej

jag har en uppgift där man först ska konvertera exponenten till binär form och sedan räkna modulo 103:

Beräkna $17^{456} (m o d 103)$ genom konvertering av exponenten till binär form.

Jag räkna ut att 456=111001000

men hur är det meningen att man ska gå vidare efter att ha tagit fram det binära talet?

Tanken är att du ska beräkna $a_n = 17^{2^n}$ . Detta kan du göra iterativt eftersom $a_{n + 1} = a_n^2$ .

Notera nu att

$17^{456} = 17^{2^{3} + 2^{6} + 2^{7} + 2^{8}} = 17^{2^{3}} \cdot 17^{2^{6}} \cdot 17^{2^{7}} \cdot 17^{2^{8}} = a_{3} \cdot a_{6} \cdot a_{7} \cdot a_{8}$

Så om man nu beräknar $a_n \text{ (mod 103)}$ så gör man så att

$a_{0} \equiv 17 (m o d 103) a_{1} \equiv a_{0}^{2} \equiv 83 (m o d 103) a_{2} \equiv a_{1}^{2} \equiv 91 (m o d 103) a_{3} \equiv a_{2}^{2} \equiv 41 (m o d 103)$

osv

Sen använder du detta för att beräkna vad $17^{456}$ är kongruent med mod 103.

Svara