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. |
Consigli
- 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.
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.