| Resto r | Quoziente q | Moltiplicatore t |
|---|
Orologio modulare
Cinque ore dopo le 9 sono le 2, perché 9 + 5 = 14 e 14 supera 12 di 2. Questa è l'aritmetica modulare: contare su un orologio che ricomincia da 0 dopo n. Scegli un'operazione, inserisci n, a e b, e la calcolatrice ti dà il risultato con ogni passaggio spiegato, dal resto di una divisione ai quadrati ripetuti e all'algoritmo di Euclide esteso, mentre l'orologio mostra come si arriva al risultato. Scegli un'operazione, poi inserisci il modulo n e i numeri a e b; funzionano i numeri interi fino a 30 cifre, anche negativi, e n può arrivare fino a 10^18. L'orologio ha n posizioni con lo 0 in alto, e la sua lancetta indica il risultato. Addizione e sottrazione sono disegnate come una spirale di b passi, con un anello per ogni giro completo; la moltiplicazione come salti di a; le potenze come le corde a, a², a³ …, che si chiudono in un ciclo; l'inverso e la divisione come i multipli che cadono su 1 o su a. I passaggi mostrano lo stesso calcolo in numeri. Fino a mod 20 viene mostrata la tabella dell'operazione; fai clic su una cella per usarne i numeri. Esempio inserisce un problema classico.
Come funziona
- Scegli un'operazione: a mod n, addizione, sottrazione, moltiplicazione, divisione, una potenza o l'inverso di a.
- Inserisci il modulo n e i numeri a e b, oppure scegli un esempio come l'ultima cifra di 7^2026 o un piccolo messaggio RSA.
- Leggi il risultato e i passaggi, segui il percorso sull'orologio e, fino a mod 20, fai clic su una cella della tabella per provarne i numeri.
Che cosa significa a mod n
a mod n è il resto della divisione di a per n: 17 mod 5 = 2, perché 17 = 3 × 5 + 2. Il resto va sempre da 0 a n − 1, anche per i numeri negativi: −7 mod 3 = 2, perché −7 = −3 × 3 + 2. Sull'orologio significa fare 7 passi indietro a partire da 0. Due numeri con lo stesso resto sono congruenti, e si scrive 17 ≡ 2 (mod 5), una notazione introdotta da Carl Friedrich Gauss nel 1801. Somme, differenze e prodotti si possono ridurre mod n a ogni passaggio, il che mantiene piccoli i numeri.
Dove si usa l'aritmetica modulare
Orologi e calendari funzionano mod 12, mod 24 e mod 7: 100 giorni dopo un mercoledì è venerdì, perché 100 mod 7 = 2. Le cifre di controllo la usano per individuare gli errori di battitura, dai codici ISBN-10 (mod 11) ai numeri delle carte di pagamento (mod 10) e agli IBAN (mod 97). I cifrari spostano le lettere mod 26, e il cifrario affine ha bisogno di un inverso mod 26 per decifrare. RSA, che protegge gran parte di Internet, cifra un messaggio m come m^e mod n e lo decifra con un'altra potenza: con n = 3233, 65^17 mod 3233 = 2790 e 2790^413 mod 3233 = 65.
Domande frequenti
Come si calcola a mod n per un numero negativo?
Aggiungi o sottrai multipli di n finché il numero è compreso tra 0 e n − 1. Per −7 mod 3: −7 + 9 = 2, quindi il risultato è 2. Alcuni linguaggi di programmazione danno invece −1 per −7 % 3, perché arrotondano il quoziente verso zero; in matematica il resto non è mai negativo.
Che cos'è un inverso modulare?
L'inverso di a mod n è il numero x con a × x ≡ 1 (mod n). L'inverso di 7 mod 26 è 15, perché 7 × 15 = 105 = 4 × 26 + 1. Esiste solo quando a e n non hanno fattori comuni, e l'algoritmo di Euclide esteso lo trova. Dividere per a mod n significa moltiplicare per il suo inverso.
Come si calcola mod n una potenza come 7^2026?
Con i quadrati ripetuti: eleva 7 al quadrato più e più volte, riducendo mod n ogni volta, per ottenere 7^1, 7^2, 7^4, 7^8 e così via, poi moltiplica quelle che compongono 2026 in binario. Bastano 10 elevamenti al quadrato e 7 moltiplicazioni invece di 2.025 moltiplicazioni, e i numeri non superano mai n². 7^2026 finisce con 9.
Perché l'orologio mostra 0 invece di 12?
Nell'aritmetica modulare i resti vanno da 0 a n − 1, quindi su un orologio con 12 posizioni mezzogiorno è 0. 12 ≡ 0 (mod 12); un orologio normale scrive semplicemente 12 dove la matematica scrive 0.
Quanto possono essere grandi i numeri?
a e b possono avere fino a 30 cifre e possono essere negativi, e il modulo può arrivare fino a 10^18. La calcolatrice lavora con numeri interi esatti nel tuo browser, quindi anche esempi delle dimensioni di RSA danno risultati esatti, e nulla viene inviato da nessuna parte.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor