Rekenen/Modulair rekenen

Modulair rekenen is een rekenmethode waarbij slechts gerekend wordt met niet-negatieve getallen met een bovengrens. Wordt een resultaat bereikt gelijk aan of groter dan de bovengrens, dan wordt de bovengrens zo vaak afgetrokken tot weer een getal kleiner dan de bovengrens verkregen wordt. Bekende voorbeelden zijn het rekenen met kloktijden en het rekenen met hoeken, Als de bovengrens m is, spreken we van rekenen modulo m.

De term modulair is afgeleid van het begrip modulus ofwel restwaarde van een deling. Bij delen hebben we gezien dat bij sommige delingen geen rest blijft en bij andere wel. Zo is 9:3=3 zonder rest, maar 10:3=3 rest 1. Die rest wordt ook modulus genoemd en men schrijft in plaats van: "de rest bij deling van 10 door 3 is 1":

10 mod 3 = 1 (10 modulo 3 is 1)

Het is gebruikelijk om te schrijven:

10 ≡ 1 (mod 3),

en te zeggen: modulo 3 zijn 10 en 1 congruent.

Omdat delen eigenlijk herhaald aftrekken is, kunnen we de modulus ook opvatten als wat overblijft nadat we zo vaak als we konden het getal waarmee we modulo rekenen afgetrokken hebben.

Zo is ook:

10 mod 4 = 2

9 mod 3 = 0

19 mod 5 = 4

We dienen wel goed onderscheid te maken tussen het modulair rekenen zoals dat gebeurt met hoeken en tijden, en het geheeltallige modulair rekenen.

Hoeken, tijden e.d.

Bij het modulair rekenen zoals met hoeken en tijden hebben de relevante grootheden een dimensie, ze worden gemeten in een of andere eenheid. Weliswaar zijn de waarden beperkt tot waarden uit het interval [0, m), waarin $m$ de betrokken bovengrens is, maar de waarden van de grootheden zijn niet beperkt tot gehele getallen. Bovendien worden slechts reeëlwaardige veelvouden van de grootheden berekend, nooit het product of quotient van twee dergelijke grootheden.

Geheeltallig modulair rekenen

Bij het geheeltallig rekenen modulo $m$ (een positief geheel getal) gaat om het rekenen met de gehele getallen $0,1,\ldots ,m-1$. Weliswaar kunnen ook andere gehele getallen voorkomen, maar deze worden in principe teruggebracht tot een van de getallen $0,1,\ldots ,m-1$ door aftrekken (of optellen) van een geheel veelvoud van $m$. Zo geldt bijvoorbeeld:

5 + 3 = 8 ≡ 2 (mod 6).

Omdat 47 ≡ 5 (mod 6) en 39 ≡ 3 (mod 6) kunnen we ook berekenen:

47 + 39 = 86 ≡ 2 (mod 6),

wat dezelfde uitkomst geeft.

Dit geldt ook voor vermenigvuldigen. Daarbij maken we het ons gemakkelijk door eerst de resultaten modulo 6 te bepalen en pas daarna te vermenigvuldigen.

47 × 39 ≡ 5 × 3 = 15 ≡ 3 (mod 6).

Anders hadden we moeten berekenen:

47 × 39 = 1833 ≡ 3 (mod 6).

Bij geheeltallig modulair rekenen is het bij optellen, aftrekken en vermenigvuldigen niet van belang of de modulus voor of na een bewerking bepaald wordt.

Bij delen moeten we voorzichtig zijn. Zo is:

2 × 2 ≡ 4 (mod 6)

maar ook is:

2 × 5 ≡ 4 (mod 6),

dus:

2 × 2 ≡ 2 × 5 (mod 6).

Zouden we nu door 2 delen, dan levert dat op:

2 ≡ 5 (mod 6),

wat niet juist is. Kennelijk kunnen we niet altijd een deling uitvoeren. Delen gaat wel goed bij rekenen modulo een priemgetal, al moeten we niet op de gewone manier delen. We krijgen dan ook geen breuken, maar weer gehele getallen. We moeten bedenken dat delen hetzelfde is als vermenigvuldigen met het omgekeerde. En modulo een priemgetal zijn alle omgekeerden weer gehele getallen.

Zo is bijvoorbeeld modulo 7:

2 × 4 ≡ 1 (mod 7),

dus zijn modulo 7 de getallen 2 en 4 elkaars omgekeerden. We berekenen daarom:

5 : 4 ≡ 5 × 2 ≡ 3 (mod 7).

Ter controle berekenen we:

3 × 4 = 12 ≡ 5 (mod 7).

Delen is bij modulair rekenen niets anders dan vermenigvuldigen met een ander geheel getal, het omgekeerde van de noemer. We geven nog een voorbeeld:

9 : 7 ≡ 9 × 8 = 72 ≡ 6 (mod 11),

want modulo 11 zijn 7 en 8 elkaars omgekeerden, immers:

7 × 8 = 56 ≡ 1 (mod 11).

Ter controle berekenen we nog:

6 × 7 = 42 ≡ 9 (mod 11).

De berekening bij delen kan ook als volgt beschreven worden. Om 9 : 7 (mod 11) te berekenen tellen we zo vaak 11 bij de teller 9 op, tot het resultaat deelbaar is door de noemer 7:

9 : 7 ≡ (9 + 33) : 7 = 42 : 7 = 6 (mod 11),

Toepassingen

De klok

We verdelen de klok in 12 uren. Stel dat het vijf uur 's morgens is en we moeten over elf uren op een afspraak zijn, 5 + 11 = 16, maar 16 staat niet op de klok. De klok gaat bij 12 aangekomen weer vrolijk vooraan bij 0 beginnen. De klok rekent modulo 12. De tijd van 16 uur is dus op de klok 16 mod 12 = 4, dit wil zeggen dat we om vier uur in de namiddag op de afspraak moeten zijn.

Hoeken

Een cirkel is verdeeld in 360 graden. Er is geen grotere hoek denkbaar. Wel kunnen we vaker ronddraaien en zo in totaal een hoek doorlopen groter dan 360°. De richting waarin we dan kijken wordt echter bepaald door modulo 360° te rekenen. Als we zeggen dat we over een hoek van 370° gedraaid zijn, is onze richting dus effectief maar met een hoek van 370 mod 360 = 10° veranderd.

RSA

Bij de asymmetrische cryptografie zoals de RSA maakt men veelvuldig gebruik van modulorekenen. Zowel voor het genereren van codes als voor het ontcijferen van codes.