Calcolatrice dell'aritmetica modulare (congruenze)
Calcolatrice per le congruenze con quattro modalità: resto elementare, addizione, sottrazione e moltiplicazione, elevamento a potenza con il metodo dei quadrati ripetuti e inverso modulare con l'algoritmo di Euclide esteso. Grazie al tipo BigInt calcola con esattezza anche i resti dei numeri negativi e le potenze con esponenti grandi.
Proprietà fondamentali dell'aritmetica modulare
| Proprietà | Descrizione |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | Nell'addizione il risultato è lo stesso sia prendendo il resto prima di sommare sia sommando prima di prendere il resto. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | Nella sottrazione il risultato può essere negativo: sommando alla fine il modulo e riprendendo il resto lo si riporta nell'intervallo fra zero e il modulo. |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | Come per l'addizione, prendere il resto durante il calcolo non altera il risultato finale. Su questa proprietà si fonda il calcolo rapido delle potenze con i quadrati ripetuti. |
| a e n coprimi ⇔ esiste l'inverso di a modulo n | Soltanto quando il massimo comune divisore fra a e n vale uno esiste, per l'algoritmo di Euclide esteso, un intero x tale che il prodotto di a per x sia congruo a uno modulo n. |
Che cos'è l'aritmetica modulare (calcolo del modulo)
L'aritmetica modulare, o calcolo delle congruenze, è un'operazione che considera esclusivamente il resto della divisione di un numero per un intero positivo chiamato modulo. Quando due interi a e b, divisi per lo stesso modulo n, danno lo stesso resto, si dice che «a e b sono congrui modulo n» e si scrive a ≡ b (mod n). Questo strumento raccoglie in un'unica pagina i calcoli più comuni legati alle congruenze, distribuiti in quattro modalità: resto elementare, addizione/sottrazione/moltiplicazione, elevamento a potenza e inverso modulare.
Tutti i calcoli interni sono eseguiti con il tipo BigInt nativo di JavaScript, così anche potenze con esponenti di centinaia di cifre o moltiplicazioni fra interi molto grandi restituiscono risultati esatti, senza errori di arrotondamento. Anche inserendo numeri negativi, lo strumento normalizza il risultato seguendo la definizione matematica della congruenza, per cui il resto è sempre compreso fra zero e il modulo: non ci si deve quindi preoccupare delle differenze di comportamento dell'operatore di resto fra un linguaggio di programmazione e l'altro.
Come si usa la calcolatrice dell'aritmetica modulare
- Scegliere la modalità Si seleziona il tipo di calcolo desiderato fra le quattro modalità: resto elementare, addizione/sottrazione/moltiplicazione, elevamento a potenza e inverso.
- Inserire gli interi A seconda della modalità scelta si inseriscono a, b e il modulo n, oppure la base e l'esponente. È possibile inserire anche numeri interi negativi.
- Scegliere l'operazione (solo nella modalità somma/differenza/prodotto) Dal menu a tendina si seleziona addizione, sottrazione o moltiplicazione.
- Leggere il risultato Il ricalcolo avviene automaticamente a ogni inserimento e vengono mostrati sia la formula sia il risultato. Se l'inverso non esiste, compare un messaggio che lo segnala.
- Ricominciare da capo Il pulsante «Cancella» svuota i campi di tutte le modalità.
Consigli per sfruttarlo al meglio
- Il resto dei numeri negativi si comporta diversamente da un linguaggio di programmazione all'altro. Questo strumento segue la definizione matematica, per cui il risultato è sempre compreso fra zero e il modulo: il resto di meno sette modulo tre è dunque due e non meno uno.
- La modalità di elevamento a potenza usa il metodo dei quadrati ripetuti e restituisce il risultato all'istante anche con esponenti di centinaia di cifre. Lo stesso algoritmo è impiegato nella cifratura e nella decifrazione della crittografia RSA.
- L'orologio è l'esempio più familiare di congruenza: le quindici, ricondotte al quadrante di dodici ore, corrispondono alle tre.
- La modalità dell'inverso funziona anche quando il modulo non è primo, purché il massimo comune divisore fra il numero e il modulo valga uno.
- Nella programmazione competitiva ricorrono di frequente problemi che chiedono, anziché il risultato per intero, il suo resto rispetto a un grande numero primo. La modalità di elevamento a potenza si presta a verificare quei calcoli.
Situazioni in cui l'aritmetica modulare torna utile
Studiare la crittografia a chiave pubblica
La cifratura e la decifrazione dell'RSA consistono nel calcolo del resto di una potenza enorme rispetto a un modulo. Con la modalità di elevamento a potenza si possono usare esponenti e moduli molto grandi e verificare direttamente la velocità del metodo dei quadrati ripetuti.
Capire il principio di progettazione delle funzioni di sintesi (hash)
Molte funzioni di sintesi usano al loro interno operazioni di resto per ricondurre un valore entro un intervallo prestabilito. Con la modalità somma/differenza/prodotto si può seguire come cambia il resto a ogni passaggio intermedio del calcolo.
Verificare il funzionamento delle cifre di controllo
Le cifre di controllo di codici ISBN, numeri di carte di credito e coordinate bancarie si ottengono dal resto, rispetto a un modulo, della somma pesata delle singole cifre. La modalità del resto elementare è utile per rifare a mano questi calcoli di verifica.
Calcolare cicli di calendario e giorni della settimana
Domande come «che giorno della settimana cade fra tot giorni» o «ogni quanti anni ricorre un anno bisestile» si possono esprimere come congruenze rispetto al modulo sette o quattro.
Verificare soluzioni di programmazione competitiva
Nei problemi che chiedono di fornire la risposta come resto rispetto a 1.000.000.007, si può confrontare il proprio risultato con quello calcolato qui usando la modalità di elevamento a potenza o quella somma/differenza/prodotto.
Glossario dell'aritmetica modulare
- Congruenza
- Una relazione della forma a ≡ b (mod n), che indica che a e b, divisi per n, danno lo stesso resto. Si usa il simbolo «≡» anziché «=» proprio perché a essere uguali non sono i valori in sé, ma i resti.
- Modulo
- Il numero per cui si divide. In questo strumento va indicato un intero pari o superiore a uno. Cambiando il modulo, cambia anche la relazione di congruenza fra gli stessi numeri.
- Operazione di modulo (resto)
- Il calcolo effettivo del resto della divisione di un numero per il modulo. Secondo la definizione matematica, il risultato è sempre compreso fra zero e il modulo, estremo escluso.
- Inverso modulare
- L'intero x che soddisfa la relazione a · x ≡ 1 (mod n). Nel mondo delle congruenze, dove la divisione non è definita, moltiplicare per l'inverso di a produce lo stesso effetto che dividere per a.
- Coprimi (primi tra loro)
- Due interi il cui massimo comune divisore vale uno. Solo quando a e n sono coprimi esiste l'inverso di a modulo n.
- Algoritmo di Euclide esteso
- Un procedimento che, oltre a calcolare il massimo comune divisore fra due numeri, trova contemporaneamente la coppia di interi (x, y) che soddisfa a · x + n · y = mcd(a, n). Viene impiegato nel calcolo della modalità dell'inverso.
- Esponenziazione rapida (quadrati ripetuti)
- Un algoritmo che, scomponendo l'esponente in base due e moltiplicando via via la base elevata al quadrato solo quando la cifra binaria corrispondente vale uno, calcola una potenza con un numero di moltiplicazioni proporzionale alle cifre binarie dell'esponente. È l'algoritmo usato nella modalità di elevamento a potenza.
- Esponenziazione modulare
- Il calcolo del resto di una potenza rispetto a un modulo. È l'operazione centrale della cifratura e della decifrazione RSA e corrisponde alla modalità di elevamento a potenza di questo strumento.
Domande frequenti
A proposito — l'aritmetica dell'orologio che sostiene la crittografia moderna
L'aritmetica modulare è spesso chiamata «aritmetica dell'orologio». Su un quadrante di dodici ore, le tredici sono «le stesse» dell'una: è esattamente la congruenza fra tredici e uno modulo dodici, cioè l'idea di considerare soltanto il resto della divisione per un modulo. Fu il matematico tedesco Carl Friedrich Gauss, nella sua opera del 1801 sulle ricerche aritmetiche, a sistemare la notazione delle congruenze, facendone uno strumento standard della matematica moderna.
Questa operazione, in apparenza elementare, sostiene l'intera sicurezza di Internet. Nella crittografia a chiave pubblica, a cominciare dall'RSA, il calcolo centrale della cifratura e della decifrazione è l'elevamento a potenza modulare, cioè il resto di una potenza enorme. Poiché esponenti e moduli contano centinaia di cifre, calcolare prima la potenza e poi il resto farebbe esplodere la complessità; con il metodo dei quadrati ripetuti bastano invece tante moltiplicazioni quante sono le cifre binarie dell'esponente e il calcolo diventa praticabile.
Anche il calcolo dell'inverso modulare con l'algoritmo di Euclide esteso è una tecnica di base largamente usata in informatica, non soltanto nella crittografia ma anche nella teoria dei codici e nella progettazione delle funzioni di sintesi. Che un'aritmetica di oltre duemila anni fa e le più moderne tecnologie di sicurezza poggino sullo stesso fondamento matematico è emblematico dell'universalità della teoria dei numeri.