| Rest r | Kvotient q | Faktor t |
|---|
Modulært ur
Fem timer efter klokken 9 er klokken 2, fordi 9 + 5 = 14, og 14 er 2 mere end 12. Det er modulær aritmetik: at tælle på et ur, der starter forfra ved 0 efter n. Vælg en operation, indtast n, a og b, og lommeregneren giver svaret med hvert trin skrevet ud, fra resten ved en division til gentagen kvadrering og den udvidede euklidiske algoritme, mens uret viser, hvordan svaret nås. Vælg en operation, og indtast derefter modulus n og tallene a og b; hele tal med op til 30 cifre virker, også negative, og n kan være op til 10^18. Uret har n positioner med 0 øverst, og viseren peger på svaret. Addition og subtraktion tegnes som en spiral på b trin med én ring for hver hel omgang; multiplikation som spring på a; potenser som korderne a, a², a³ …, der lukker sig til en cyklus; den inverse og division som de multipla, der lander på 1 eller på a. Trinnene viser den samme udregning i tal. Op til mod 20 vises tabellen for operationen; klik på en celle for at bruge dens tal. Eksempel udfylder en klassisk opgave.
Sådan virker det
- Vælg en operation: a mod n, addition, subtraktion, multiplikation, division, en potens eller den inverse af a.
- Indtast modulus n og tallene a og b, eller vælg et eksempel som det sidste ciffer i 7^2026 eller en lille RSA-meddelelse.
- Aflæs svaret og trinnene, følg vejen på uret, og klik op til mod 20 på en celle i tabellen for at prøve dens tal.
Hvad a mod n betyder
a mod n er resten, når a divideres med n: 17 mod 5 = 2, fordi 17 = 3 × 5 + 2. Resten er altid fra 0 til n − 1, også for negative tal: −7 mod 3 = 2, fordi −7 = −3 × 3 + 2. På uret betyder det at gå 7 trin baglæns fra 0. To tal med samme rest er kongruente, skrevet 17 ≡ 2 (mod 5), en notation, som Carl Friedrich Gauss indførte i 1801. Summer, differenser og produkter kan reduceres mod n ved ethvert trin, hvilket holder tallene små.
Hvor modulær aritmetik bruges
Ure og kalendere regner mod 12, mod 24 og mod 7: 100 dage efter en onsdag er det fredag, fordi 100 mod 7 = 2. Kontrolcifre bruger det til at fange tastefejl, fra ISBN-10-numre (mod 11) til betalingskortnumre (mod 10) og IBAN-numre (mod 97). Chifre forskyder bogstaver mod 26, og det affine chiffer kræver en invers mod 26 for at dekryptere. RSA, som beskytter en stor del af internettet, krypterer en meddelelse m som m^e mod n og dekrypterer med en anden potens: med n = 3233 er 65^17 mod 3233 = 2790 og 2790^413 mod 3233 = 65.
Ofte stillede spørgsmål
Hvordan udregner man a mod n for et negativt tal?
Læg multipla af n til eller træk dem fra, indtil tallet ligger mellem 0 og n − 1. For −7 mod 3: −7 + 9 = 2, så svaret er 2. Nogle programmeringssprog giver i stedet −1 for −7 % 3, fordi de afrunder kvotienten mod nul; i matematikken er resten aldrig negativ.
Hvad er en modulær invers?
Den inverse af a mod n er det tal x, for hvilket a × x ≡ 1 (mod n). Den inverse af 7 mod 26 er 15, fordi 7 × 15 = 105 = 4 × 26 + 1. Den findes kun, når a og n ingen fælles faktor har, og den udvidede euklidiske algoritme finder den. At dividere med a mod n betyder at multiplicere med dens inverse.
Hvordan kan en potens som 7^2026 udregnes mod n?
Ved gentagen kvadrering: kvadrer 7 igen og igen, og reducer mod n hver gang, så du får 7^1, 7^2, 7^4, 7^8 og så videre, og multiplicer derefter dem, der tilsammen udgør 2026 i binær form. Det kræver 10 kvadreringer og 7 multiplikationer i stedet for 2.025 multiplikationer, og tallene bliver aldrig større end n². 7^2026 ender på 9.
Hvorfor viser uret 0 i stedet for 12?
I modulær aritmetik går resterne fra 0 til n − 1, så på et ur med 12 positioner er middag 0. 12 ≡ 0 (mod 12); et almindeligt ur skriver bare 12, hvor matematikken skriver 0.
Hvor store kan tallene være?
a og b kan have op til 30 cifre og må være negative, og modulus kan være op til 10^18. Lommeregneren arbejder med eksakte hele tal i din browser, så selv eksempler i RSA-størrelse giver eksakte svar, og intet sendes nogen steder hen.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor