Machtsverheffingen bij modulair rekenen

We spreken van “modulair rekenen” als we uitsluitend met gehele getallen werken tussen 0 en een bepaalde bovengrens die we de modulus noemen.  De verzameling getallen waarvan we ons bedienen is dus 0, 1, 2, … tot modulus –1.  Het getal dat komt na “modulus – 1” is gewoon opnieuw 0.

Een voorbeeld: Als we werken met modulus 7, dan beschikken we over de getallen 0, 1, 2, 3, 4, 5 en 6. Wanneer we 4 + 4 (mod 7) berekenen dan is het resultaat 1.  In klassieke wiskunde zou het resultaat 8 zijn, maar als we werken met modulus 7, dan komt er na de 6 een 0 en dan een 1.  Een van de gevolgen van modulair rekenen is, dat ongeacht wat je doet (optellen, vermenigvuldigen, machtsverheffingen, …) en met welke getallen je dat doet, je resultaat altijd tussen 0 en de modulus zal liggen.

We gaan nu machtsverheffingen uitvoeren bij modulair rekenen. Neem bijvoorbeeld de 23e macht van 87 modulus 34. We zijn zeker (zie hierboven) dat het resultaat een getal zal zijn tussen 0 en 33.  Maar zonder speciale technieken moeten we toch eerst uitrekenen hoeveel de 23e macht is van 87 om daarna de modulus te kunnen toepassen. Het resultaat van 87 tot de 23e macht is 406389810477299000000000000000000000000000000. Dat gaan we nu delen door 34 en de rest na deling is onze oplossing.  Heel veel rekenmachines en zelfs Excel kunnen met dergelijke grote getallen niet overweg.

Om het resultaat van een grote machtsverheffing bij modulair rekenen te vinden bestaat er gelukkig een handig algoritme. En dat gaat als volgt. Vermenigvuldig je basisgetal (87) met 1, het resultaat van deze bewerking deel je door de modulus en je neemt de rest na deling. Je herhaalt deze procedure maar nu vermenigvuldig je je basisgetal NIET met 1 maar met de rest na deling van de vorige ronde. Je herhaalt deze procedure even vaak als de exponent groot is. In ons geval dus 23 keer. In onze situatie krijgen we dus

Stap 1:  1  * 87 (mod 34) =  19
Stap 2: 19 * 87 (mod 34) = 21
Stap 3: 21 * 87 (mod 34) = 25
…
Stap 23: 13 * 87 (mod 34) = 9

Het grootste getal waarmee je geconfronteerd kan worden bij dit algoritme is het basisgetal * de modulus (2 958 in ons geval).

Dit algoritme is trouwens erg makkelijk in programmacode te gieten:

int mymodpow(int basis, int exponent, int modulus)

{

       int result = 1;

       for (int teller = 1; teller <= exponent; teller++)

           result = (result * basis) % modulus;

       return result;

 }

Deze blogpost past in een reeks blogposts over cryptografie. Machtsverheffingen bij modulair rekenen is een techniek die gebruikt wordt oa. in het RSA algoritme (asymmetrische encryptie) en Diffie Hellman (protocol voor geheime sleuteluitwisseling).