Resultat
Utan mod
Hela varv
sgd(a, n)

    Mer om moduloräkning

    Modulär klocka

    Fem timmar efter klockan 9 är klockan 2, eftersom 9 + 5 = 14 och 14 är 2 mer än 12. Det är moduloräkning: att räkna på en klocka som börjar om från 0 efter n. Välj en operation, ange n, a och b, så ger kalkylatorn svaret med varje steg utskrivet, från resten vid en division till upprepad kvadrering och den utvidgade euklidiska algoritmen, medan klockan visar hur svaret nås. Välj en operation och ange sedan modulen n och talen a och b; heltal med upp till 30 siffror fungerar, även negativa, och n kan vara upp till 10^18. Klockan har n positioner med 0 högst upp, och visaren pekar på svaret. Addition och subtraktion ritas som en spiral med b steg, en ring för varje helt varv; multiplikation som hopp på a; potenser som kordorna a, a², a³ …, som sluter sig till en cykel; inversen och division som de multipler som landar på 1 eller på a. Stegen visar samma beräkning med tal. Upp till mod 20 visas operationens tabell; klicka på en cell för att använda dess tal. Exempel fyller i ett klassiskt problem.

    Hur det fungerar

    1. Välj en operation: a mod n, addition, subtraktion, multiplikation, division, en potens eller inversen av a.
    2. Ange modulen n och talen a och b, eller välj ett exempel som sista siffran i 7^2026 eller ett litet RSA-meddelande.
    3. Läs svaret och stegen, följ vägen på klockan och klicka upp till mod 20 på en cell i tabellen för att prova dess tal.

    Vad a mod n betyder

    a mod n är resten när a delas med n: 17 mod 5 = 2, eftersom 17 = 3 × 5 + 2. Resten ligger alltid från 0 till n − 1, även för negativa tal: −7 mod 3 = 2, eftersom −7 = −3 × 3 + 2. På klockan betyder det att gå 7 steg bakåt från 0. Två tal med samma rest är kongruenta, skrivet 17 ≡ 2 (mod 5), ett skrivsätt som Carl Friedrich Gauss införde 1801. Summor, differenser och produkter kan reduceras mod n i varje steg, vilket håller talen små.

    Var moduloräkning används

    Klockor och kalendrar räknar mod 12, mod 24 och mod 7: 100 dagar efter en onsdag är det fredag, eftersom 100 mod 7 = 2. Kontrollsiffror använder det för att upptäcka skrivfel, från ISBN-10-nummer (mod 11) till kortnummer (mod 10) och IBAN (mod 97). Chiffer förskjuter bokstäver mod 26, och det affina chiffret behöver en invers mod 26 för att dekryptera. RSA, som skyddar en stor del av internet, krypterar ett meddelande m som m^e mod n och dekrypterar med en annan potens: med n = 3233 är 65^17 mod 3233 = 2790 och 2790^413 mod 3233 = 65.

    Ofta ställda frågor

    Hur beräknar man a mod n för ett negativt tal?

    Addera eller subtrahera multipler av n tills talet ligger mellan 0 och n − 1. För −7 mod 3: −7 + 9 = 2, så svaret är 2. Vissa programspråk ger i stället −1 för −7 % 3, eftersom de avrundar kvoten mot noll; i matematiken är resten aldrig negativ.

    Vad är en modulär invers?

    Inversen av a mod n är det tal x för vilket a × x ≡ 1 (mod n). Inversen av 7 mod 26 är 15, eftersom 7 × 15 = 105 = 4 × 26 + 1. Den finns bara när a och n saknar gemensam faktor, och den utvidgade euklidiska algoritmen hittar den. Att dividera med a mod n betyder att multiplicera med dess invers.

    Hur kan en potens som 7^2026 beräknas mod n?

    Med upprepad kvadrering: kvadrera 7 om och om igen och reducera mod n varje gång, så att du får 7^1, 7^2, 7^4, 7^8 och så vidare, och multiplicera sedan de potenser som tillsammans bygger upp 2026 i binär form. Det kräver 10 kvadreringar och 7 multiplikationer i stället för 2 025 multiplikationer, och talen blir aldrig större än n². 7^2026 slutar på 9.

    Varför visar klockan 0 i stället för 12?

    I moduloräkning går resterna från 0 till n − 1, så på en klocka med 12 positioner är klockan tolv på dagen lika med 0. 12 ≡ 0 (mod 12); en vanlig klocka skriver bara 12 där matematiken skriver 0.

    Hur stora kan talen vara?

    a och b kan ha upp till 30 siffror och får vara negativa, och modulen kan vara upp till 10^18. Kalkylatorn räknar med exakta heltal i din webbläsare, så även exempel i RSA-storlek ger exakta svar, och ingenting skickas någonstans.

    Redo att prova det?

    Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

    Gå till Editor