Modulær aritmetik forklaret
Alle bruger allerede modulær aritmetik: 10 timer efter klokken 8 er klokken 6, og dagen efter søndag er mandag. Optælling, der starter forfra fra 0 efter n trin, viser sig at have sin egen fuldstændige aritmetik med regler, overraskelser og en central plads i talteorien og i den kryptografi, der beskytter internettet.
Rester og kongruens
Divider a med n, og behold kun resten: det er a mod n, et tal fra 0 til n − 1. 26 mod 7 = 5, fordi 26 = 3 × 7 + 5. Tal med samme rest opfører sig ens mod n, så vi kalder dem kongruente: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss indførte denne notation i sin Disquisitiones Arithmeticae fra 1801, og den gjorde Fermats og Eulers gamle iagttagelser til en selvstændig aritmetik. På et ur med n positioner lander hvert helt tal på sin rest; de hele omgange glemmes.
Addition, subtraktion og multiplikation
De tre almindelige regnearter virker som sædvanligt, og du må reducere mod n, når du vil: resten af en sum er resten af summen af resterne, og det samme gælder differenser og produkter. For at finde det sidste ciffer i 37 × 48 multiplicerer du kun de sidste cifre: 7 × 8 = 56, så det ender på 6. Det er det, der gør modulær aritmetik så nyttig for computere: uanset hvor store tallene er, overstiger mellemresultaterne aldrig n².
Division kræver en invers
Division er undtagelsen. 2 × 3 ≡ 2 × 8 (mod 10), da begge er 6 mod 10, men 3 og 8 er forskellige, så man kan ikke bare forkorte 2-tallet væk. At dividere med a betyder at multiplicere med dens inverse, det tal x, for hvilket a × x ≡ 1, og den findes netop, når a og n ingen fælles faktor har. Den udvidede euklidiske algoritme finder den: den udfører Euklids divisionstrin for den største fælles divisor og holder styr på en faktor ved hvert trin, så når resten når 1, er faktoren den inverse. Når n er et primtal, har alle tal undtagen 0 en invers, og division virker altid.
Potenser, Fermat og Euler
Potenser gentager sig. Tag potenserne af 3 mod 7: 3, 2, 6, 4, 5, 1, og så 3 igen. Længden af den cyklus er ordenen af 3. I 1640 bemærkede Pierre de Fermat, at der for et primtal p gælder a^(p − 1) ≡ 1 (mod p), når p ikke går op i a, så enhver orden går op i p − 1. Leonhard Euler beviste det og udvidede det til ethvert n, hvor p − 1 erstattes af antallet af værdier, der er indbyrdes primiske med n. Enorme potenser udregnes ved gentagen kvadrering: a, a², a⁴, a⁸ …, hver kvadratet af den foregående, reduceret mod n, og derefter multipliceret efter eksponentens binære cifre.
Kontrolcifre og kalendere
Modulær aritmetik fanger fejl. Det sidste ciffer i et ISBN-10 vælges, så en vægtet sum af alle ti cifre er et multiplum af 11, så ethvert enkelt forkert ciffer og enhver ombytning af to naboer opdages. Betalingskortnumre bruger Luhn-kontrollen mod 10 og IBAN-numre en kontrol mod 97. Kalendere går mod 7: ugedagen for enhver dato kan regnes ud med nogle få rester, og sådan virker evighedskalendere og dommedagsreglen.
Kryptografi
Moderne kryptografi bygger på modulære potenser, der er lette at udregne og svære at gøre om. I Diffie–Hellman-nøgleudvekslingen fra 1976 bliver to personer enige om en fælles hemmelighed over en åben linje ved at udveksle potenser modulo et stort primtal. RSA, offentliggjort i 1977 af Rivest, Shamir og Adleman, krypterer en meddelelse m som m^e mod n, hvor n er produktet af to store primtal, og dekrypterer med en anden eksponent d, som kun den, der kender de to primtal, kan udregne. I lærebogseksemplet er n = 3233 = 61 × 53, e = 17 og d = 413: 65 bliver til 2790, og 2790 bliver til 65 igen.
Udforsk det selv
Åbn det modulære ur for at udregne a mod n, summer, differenser, produkter, potenser, inverse og kvotienter mod n for tal med op til 30 cifre. Hvert svar kommer med sine trin: divisionen med rest, potenserne fra gentagen kvadrering eller tabellen fra den udvidede euklidiske algoritme. Uret tegner, hvordan svaret nås, fra spiralen ved en addition til potensernes cyklus, og for små n viser tabellen for operationen alle svarene på én gang.
Ofte stillede spørgsmål
Hvad betyder symbolet ≡?
a ≡ b (mod n) siger, at a og b giver samme rest ved division med n, eller, hvad der er det samme, at n går op i a − b. 38 ≡ 2 (mod 12), fordi 38 − 2 = 36 er et multiplum af 12.
Er mod det samme som operatoren % i programmering?
For positive tal, ja. For negative tal returnerer mange sprog, såsom C, Java og JavaScript, en negativ rest: −7 % 3 er −1 dér, mens −7 mod 3 = 2. Pythons % følger den matematiske konvention for et positivt n.
Hvad er ordenen af et tal mod n?
Det mindste k > 0 med a^k ≡ 1 (mod n). Den findes kun, når a og n ingen fælles faktor har. Ordenen af 2 mod 7 er 3, fordi 2³ = 8 ≡ 1, og ordenen af 3 mod 7 er 6, så potenserne af 3 gennemløber alle rester forskellige fra nul: 3 er en primitiv rod mod 7.
Hvem opfandt modulær aritmetik?
Rester blev brugt længe før, for eksempel i den kinesiske restsætning fra det 3. til 5. århundrede og af Fermat og Euler. Gauss gjorde det til en systematisk aritmetik med notationen for kongruenser i 1801.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn det modulære ur