WisFaq!

Stelling van Euler

128³⁴³ mod 527 = 2 mod 527.
Maar hoe kan ik dit uitrekenen?

Ik weet ook dat (527)=(16·30) = 480
De vorige keer kreeg dit als hulp.
((128⁷)⁷)⁷.
Maar wat heb ik hier precies aan?

mike
14-1-2003

Antwoord

Beste Mike,

Voor het berekenen van het modulo resultaat van een exponentiatie zijn een aantal methoden. (In het engels heet deze operatie trouwens modular exponentiation, maar in het nederlands heb ik er nog niet echt een mooie benaming voor gevonden).

Dit is een erg belangrijke berekening in bijvoorbeeld in de cryptografie, waar deze modular exponentiation met zeer grote getallen wordt uitgevoerd. Daarom is er ook vaak gezocht naar een efficiente manier om dit te berekenen. Nu is er natuurlijk wel een verschil in benadering van hele grote getallen en iets met de hand uitrekenen, maar toch kun je methoden in beide gevallen gebruiken.

De meest simpele aanpak zou kunnen zijn om eerst te exponentieren en dan de rest te bepalen.
Bijvoorbeeld:
4² mod 5:
4² = 16
16 mod 5 = 1
Maar zelfs in jouw eigenlijk nog relatief kleine getallen voorbeeld is dat al niet meer te doen.

Een ander manier zou zijn om tussen de vermenigvuldigingen (exponentieren is tenslotte herhaald vermenigvuldigen) al de rest uit te rekenen.
Bijvoorbeeld:
3³ mod 5
3 · 3 = 9; 9 mod 5 = 4
4 · 5 = 20; 20 mod 5 = 0
Maar dit is ook al niet meer te doen in jouw voorbeeld omdat je dan 343 vermenigvuldigingen en mod operaties zou moeten uitvoeren.

Maar......er zijn een aantal regeltjes die je kunnen helpen om sneller je antwoord te berekenen.

x^a·x^b = x^a+b
(x^a)^b = x^a·b

De stelling van Euler maakt het mogelijk om de exponent te vereenvoudigen:
a^$\phi$(n) $\equiv$1 mod n

We kunnen de basis en de exponent dus op de volgende manier vereenvoudigen:
a^b $\equiv$ (a mod n)^{b mod $\phi$(n)} mod n
(ga zelf na!)

Maar in je voorbeeld hebben we dus niets aan de stelling van Euler omdat je exponent niet groot genoeg is.

In dit geval kun je gebruik maken van de bijzondere vorm van de exponent. Je krijgt dan het volgende:
128² mod 527: 128 · 128 $\equiv$ 16384 $\equiv$47
128⁴ mod 527: 47 · 47 $\equiv$ 2209 $\equiv$101
128⁶ mod 527: 47 · 101 $\equiv$ 4747 $\equiv$4
128⁷ mod 527: 4 · 128 $\equiv$ 512

512² mod 527: 512 · 512 $\equiv$ 262144 $\equiv$225
512⁴ mod 527: 225 · 225 $\equiv$ 50625 $\equiv$33
512³ mod 527: 512 · 225 $\equiv$ 115200 $\equiv$314
512⁷ mod 527: 314 · 33 $\equiv$ 10362 $\equiv$349

349² mod 527: 349 · 349 $\equiv$ 121801 $\equiv$64
349⁴ mod 527: 64 · 64 $\equiv$ 4096 $\equiv$407
349⁶ mod 527: 407 · 64 $\equiv$ 26048 $\equiv$225
349⁷ mod 527: 349 · 225 $\equiv$ 78525 $\equiv$2

Een andere wat meer algemene manier die ook veel in software en hardware wordt gebruikt is left-to-right exponentiation. Dit maakt gebruik van de binaire representatie van de exponent en dat binair gezien vermenigvuldigen met 2 betekent een nul erachter plakken.
Dan moet je voor elk stapje kwadrateren en als er een 1 in de exponent staat vermenigvuldigen.
Dit betekent in jouw voorbeeld:
343 = 101010111

1: 128
0: 128 · 128 $\equiv$ 47 (alles mod 527)
1: 47 · 47 $\equiv$ 101
101 · 128 $\equiv$280
0: 280 · 280 $\equiv$404
1: 404 · 404 $\equiv$373
373 · 128 $\equiv$314
0: 314 · 314 $\equiv$47
1: 47 · 47 $\equiv$101
101 · 128 $\equiv$280
1: 280 · 280 $\equiv$404
404 · 128 $\equiv$ 66
1: 66 · 66 $\equiv$ 140
140 · 128 $\equiv$ 2

Je rekent dus achtereenvolgens exponenten uit:
2 : 10
4 : 100
5 : 101
10: 1010
20: 10100
21: 10101
42: 101010
84: 1010100
85: 1010101
170:10101010
171:10101011
342:101010110
343:101010111

Er bestaan dan op deze methoden ook weer verbeteringen. Ik denk dat je zo wel een aardig overzicht hebt van manieren om dit vraagstuk aan te pakken. Wil je nog meer weten dan kun je bijvoorbeeld gaan zoeken op de volgende trefwoorden(helaas in het engels):

• right-to-left exponentiation
• sliding window exponentiation
• exponent recoding
• modular reduction
• Chinese Remainder Theorem
• Montgomery Exponentiation

gm
16-1-2003