] >
Machtsverheffen in een ring is herhaald vermenigvuldigen:
Het berekenen van is terug te brengen tot twee operaties: kwadrateren en vermenigvuldigen met . Om dat in te zien kun je het best de exponent binair schrijven. Bij kwadrateren gaat over in . In de binaire notatie voor betekent dit dat er een achter komt. Je kunt er een achter krijgen door eerst te kwadrateren en vervolgens met te vermenigvuldigen: gaat dan over in . De binaire notatie van vertelt je precies wat je achtereenvolgens moet doen om bij te komen.
11.11 Voorbeeld. We berekenen in (of ). Bepaal eerst de binaire notatie van . Deze is , of kortweg . We hebben (de exponenten links zijn steeds binair):
Dus .
Bij rekenen modulo kunnen de tussentijdse resultaten vervangen worden door hun resten bij deling door .
11.12 Voorbeeld. We berekenen nu in . We hebben (de exponenten links zijn steeds binair, verder gebruiken we in plaats van om duidelijk te maken dat we met representanten rekenen):
Dus . Bij dit rekenwerk wordt niet met zulke grote getallen gerekend als in het vorige voorbeeld. Natuurlijk kunnen we eerst berekenen en dan pas van het resultaat de rest bij deling door bepalen. Bij loopt deze werkwijze uit de hand, in tegenstelling tot de methode waarbij tussentijds de rest bij deling door wordt bepaald.
We voegen de beschreven methode van machtsverheffen in toe aan de module arithmetics.py:
De functie binary zet een getal om in het binaire stelsel en deze functie wordt aangeroepen in modpower.
Python kent overigens de functie pow(x,y,z) die hetzelfde resultaat geeft als modpower. Daarom zullen we verder pow gebruiken.
In Voorbeeld 11.12 zagen we dat in geldt (de exponent is hier decimaal, binair is hij ). In Paragraaf 11.5 zullen we van zulke verschijnselen meer begrijpen. De daar behandelde Stelling van Euler zegt dat in dit geval . In Paragraaf 11.6 zullen we zonder veel rekenwerk inzien dat .