WisFaq!

Modulo met macht

Hallo ,
ik moet volgende vraag kunnen oplossen in stappen ,
61⁵⁶ mod 33 = ?
ik weet niet echt met welke manier het beste is ,
zelf heb ik al geprobeert
61⁵⁶ mod 33 = 61³² mod 33 · 61¹⁶ mod 33 ·61⁸ mod 33
= 3 · 4 · 61⁸ mod 33

bij de voorbeelden die ik heb staan komt het steeds uit dat de laatste term van de macht 1 is , nu weet ik niet of dit verplicht is ofzo , maar ik kan maar niet aan 16 als uitkomst komen ,

graag enige hulp

mvg Dimitri

Dimitri De Proft
5-12-2009

Antwoord

Je hebt al uitgezocht dat je 61³² mod 33 · 61¹⁶ mod 33 ·61⁸ mod 33 moet berekenen.
Dit zijn niet zomaar willekeurige exponenten, maar de exponenten zijn machten van 2.
Bedenk nu het volgende: voor iedere a en e geldt dat a^e·a^e=a^2e.
Je kunt dus die machten met exponenten die zelf weer machten van twee zijn heel makkelijk generen door herhaald te kwadrateren.
Ik krijg dan onderstaand tabelletje:

61 mod 33=28
61² : 28²=784 mod 33=25
61⁴ : 25²=625 mod 33=31
61⁸ : 31²=961 mod 33=4
61¹⁶ : 4²=16 mod 33=16
61³² : 16²=256 mod 33=25

Kennelijk is dan 61⁵⁶ mod 33=25·16·4 mod 33=1600 mod 33=16.

Hoe je nu eenvoudig kunt weten welke exponenten je moet kiezen is een ander verhaal. Dat op 1 uitkomen zou daar wel eens mee te maken kunnen hebben.

hk
6-12-2009