Inverso modulare: l'elemento che "divide" mod m

L'inverso modulare di a rispetto al modulo m è l'intero x tale che a · x ≡ 1 (mod m). Esiste se e solo se gcd(a, m) = 1, cioè se a e m sono coprimi. Quando esiste, è unico in {0, 1, ..., m−1} e si denota a⁻¹ mod m. Esempi: 3⁻¹ mod 7 = 5 (perché 3·5 = 15 = 2·7 + 1); 10⁻¹ mod 17 = 12 (10·12 = 120 = 7·17 + 1). Non esiste 2⁻¹ mod 4 perché gcd(2,4) = 2 ≠ 1. L'inverso modulare è il fondamento dell'aritmetica in ℤ/mℤ usata in crittografia (RSA, ElGamal, Diffie-Hellman), teoria dei codici e algoritmi numerici.

Algoritmo Euclideo esteso

Il metodo più efficiente per calcolare a⁻¹ mod m è l'algoritmo Euclideo esteso, che trova coefficienti di Bezout x, y tali che a·x + m·y = gcd(a, m). Se gcd(a,m)=1, allora a·x ≡ 1 (mod m), quindi x mod m è l'inverso cercato. Complessità O(log min(a,m)), molto più veloce del brute-force O(m). Esempio a=3, m=7: 7 = 2·3 + 1 → 1 = 7 − 2·3 → x = −2 ≡ 5 (mod 7). Quindi 3⁻¹ ≡ 5 (mod 7).

Esponenziazione modulare a^b mod m

Calcolare a^b quando b è grande è impraticabile con moltiplicazioni dirette (il risultato può avere miliardi di cifre). L'esponenziazione binaria (square-and-multiply) riduce il costo a O(log₂ b) moltiplicazioni modulari: scrivi b in binario, scandisci bit per bit, quadra a ogni passo, moltiplica per a se il bit è 1, riduci mod m ogni volta. Esempio 7²¹ mod 100: 21 = 10101₂, risultato 7 (fase 0) → 49 → 43 → 49 → 43 → 07. Fondamentale in RSA (a^d mod n per decrittazione) e primality testing (Miller-Rabin, Fermat).

Teorema di Fermat piccolo e Eulero

Se p è primo e gcd(a,p)=1, allora a^(p−1) ≡ 1 (mod p) (Fermat). Quindi l'inverso è a⁻¹ ≡ a^(p−2) mod p. Eulero generalizza: per m qualsiasi, a^φ(m) ≡ 1 (mod m) se gcd(a,m)=1, dove φ è la funzione toziente (numero di interi in [1,m] coprimi con m). Per m = p·q prodotto di due primi distinti (RSA), φ(m) = (p−1)(q−1). Teorema cinese del resto consente di decomporre calcoli mod m in calcoli mod p e mod q, più veloci.

Congruenze lineari a·x ≡ b (mod m)

Una congruenza a·x ≡ b (mod m) ha soluzioni sse d = gcd(a, m) divide b. In tal caso esistono esattamente d soluzioni distinte modulo m. Procedura: dividi la congruenza per d ottenendo a'·x ≡ b' (mod m'), dove a'=a/d, b'=b/d, m'=m/d; l'unica soluzione è x₀ = a'⁻¹ · b' (mod m'). Le d soluzioni originali sono x₀, x₀+m', x₀+2m', ..., x₀+(d−1)m' (mod m).

Applicazioni in crittografia

RSA: chiave privata d = e⁻¹ mod φ(n), con n=pq e e esponente pubblico tipicamente 65537. Decrittazione: m = c^d mod n. Firma digitale: s = H(m)^d mod n. ElGamal e DSA usano inverso mod q (ordine del gruppo). Curve ellittiche (ECDSA, Ed25519): scalar multiplication usa esponenziazione modulare su campi finiti GF(p) e GF(2ⁿ). Hashing crittografico a velocità elevata richiede moltiplicazioni modulari su parole di 32-64 bit.

Altri usi

Algoritmi hash a moduli primi (Rabin-Karp, ricerca di stringhe); controllo degli errori (CRC con polinomi in GF(2)); codici Reed-Solomon (operazioni in GF(2^m)); generatori pseudo-casuali lineari (LCG: Xₙ₊₁ = a·Xₙ + c mod m); teoria dei grafi (ciclicità in Z/nZ); crittovalute (secp256k1 in Bitcoin/Ethereum, pairings in BLS12-381); blockchain (zk-SNARK su curve ellittiche amichevoli); decimazione di segnali (resampling in DSP).

Come usare

Seleziona la modalità: Inverso (a, m → a⁻¹ mod m), Esponenziazione (a, b, m → a^b mod m), Euclideo esteso (a, b → gcd, x, y tale che ax+by=gcd), Congruenza lineare (a, b, m → tutte le soluzioni di ax≡b mod m). Interi positivi; m ≥ 2.

L'aritmetica modulare, dall'orologio a RSA

L'aritmetica modulare, formalizzata da Carl Friedrich Gauss nelle Disquisitiones Arithmeticae del 1801, è l'aritmetica dei resti: come le ore su un quadrante, i numeri "tornano indietro" dopo aver raggiunto il modulo. L'inverso modulare è l'operazione che rende questo mondo un campo quando il modulo è primo, permettendo di "dividere". Su questa struttura si fondano la crittografia RSA, il protocollo Diffie-Hellman per lo scambio di chiavi e le firme digitali che autenticano ogni transazione bancaria e ogni connessione sicura HTTPS. Nei corsi di crittografia dei Politecnici italiani, l'Euclide esteso e l'inverso modulare sono tra i primi algoritmi insegnati.

Il teorema cinese del resto

Un'applicazione classica dell'inverso modulare è la risoluzione dei sistemi di congruenze con il teorema cinese del resto, noto già ai matematici cinesi del III secolo. Permette di ricostruire un numero conoscendone i resti rispetto a moduli coprimi, ed è usato oggi per accelerare i calcoli RSA, per la generazione di numeri pseudocasuali e nell'aritmetica dei grandi interi. Il calcolatore fornisce i mattoni di base — inverso, Bézout e congruenze lineari — su cui questi risultati si costruiscono.

Aggiornato a luglio 2026