Aritmetica modulare

I moduli nella vita di tutti i giorni

Cominciamo subito da un esempio reale – non per me, in effetti, e probabilmente per nessuno in questo decennio; ma dovrebbe essere comunque comprensibile. Se una persona entra in discoteca alle 23 e ci sta cinque ore, quando ne esce? Alle 4 del giorno dopo, più o meno in grado di intendere e volere. Ma 23+5=28, non 4! Il nostro discotecaro ha anche perso la facoltà di contare? Ovviamente no, le 4 sono nella giornata successiva e i conti tornano. Però se stiamo guardando un'orologio digitale che non indica la data, l'operazione 23+5=4 è perfettamente corretta. Un matematico direbbe che la somma è corretta modulo 24; se vogliamo usare concetti più terra terra possiamo dire che il resto della divisione per 24 dell'operazione 23+5 è 4. Storicamente in effetti l'operazione di modulo è nata per utilizzare i resti, e solo in seguito è stata assorbita nella teoria dei gruppi, di cui però al momento non parlo.
Altri esempi di occorrenze "naturali" dei moduli sono l'orologio analogico con le lancette, che considera i numeri modulo 12, e la trigonometria, dove gli angoli sono calcolati modulo 360 gradi (o 2π radianti... ma di nuovo andiamo fuori strada, soprattutto perché in questo caso non stiamo più dividento per un numero intero). La prova del nove, anche se a prima vista non ce ne accorgiamo perché non facciamo esplicitamente le divisioni, lavora con i numeri modulo 9; se ci limitiamo a guardare l'ultima cifra, quella più a destra, nei calcoli stiamo in realtà lavorando modulo 10. Infine, se vogliamo fare le cose in grande e guardare attentamente i sistemi di crittografia a chiave pubblica, scopriremo che anche in quel caso si usano i moduli, anche se di numeri parecchio più grandi.

Sommiamo, ma non confrontiamo

Se i numeri modulo 12 sono i resti della divisione per 12 di un numero intero qualunque, è chiaro che i possibili valori sono esattamente 12, quelli da 0 a 11. Più in generale, i numeri modulo k vanno da 0 a k-1. "Ma nell'orologio non ci sono le ore 0! Sono le 12!", mi dirà qualcuno. La risposta è "sì, ma cosa importa?" In effetti se lavoriamo modulo 12 allora 0 e 12 sono la stessa cosa, visto che la differenza tra di loro è 12... e dodici diviso dodici dà resto zero. Se vogliamo essere pignoli come un Vero Matematico, dobbiamo dire che 0 e 12 sono congrui (modulo 12); non arrabbiatevi però troppo se mi scapperà qualche "uguale" al posto di "congruo".
All'atto pratico è come se avessimo suddiviso tutti i numeri, positivi e negativi, in dodici classi distinte come gli animali del calendario cinese, e poi per ciascuna classe scegliamo un rappresentante. Convenzionalmente si usano i numeri da 0 a k-1 perché semplificano le operazioni, ma non c'è nulla di male in certi casi a prendere quelli da 1 a k; in altri casi, ad esempio quando si usano i numeri modulo 3, si può anche scegliere di prendere come rappresentanti 0, 1 e -1 "per ragioni di simmetria".

Tabella 1: somma modulo 12

Che ci facciamo con questi numeri? Beh, iniziamo con le quattro operazioni! Per la somma, nella tabella 1 vediamo cosa succede con la somma modulo 12. Sarete d'accordo con me che non è che la cosa sia così eccitante: la tabella sembra più che altro uno di quelle strisce di led dove scorrono le parole. Lo zero si comporta come ci si aspetta da lui; l'unica cosa che potrebbe sembrarci strana è che il risultato della somma è minore dei due addendi, come in 8+5=1. Ma è proprio così? Stiamo dando per scontato che i moduli possano essere ordinati. Ma questo non è affatto vero: anche in un orologio, uno può dire che le cinque sono "dopo" l'una, ma un altro può ribattere di no, che l'una del pomeriggio sono dopo le cinque del mattino, e non si vede come dargli torto. Potremmo pensare di dire "sì, ma dalle cinque all'una c'è più distanza che tra l'una e le cinque, e quindi c'è un ordine implicito". Ma è meglio lasciar perdere, visto che con questo "ragionamento" 5 è maggiore di 1, 9 è maggiore di 5, ma 1 è maggiore di 9 modulo 12: e questo non sembra troppo bello.

La differenza si calcola esattamente come la somma. Si potrebbe scrivere una tabellina apposta, e lo potrei lasciare come esercizio per il lettore: ma probabilmente non ne vale la pena, visto che è facile usare "alla rovescia" la tabellina per somma scegliendo il sottraendo nella riga in alto, cercando il minuendo all'interno della colonna ad esso corrispondente, e leggendo il risultato sulla colonna a sinistra. Ma c'è un altro modo per fare una sottrazione! Possiamo infatti scrivere a-b nella forma a+(-b). A prima vista non sembrerebbe esserci chissà quale vantaggio, anzi: ma questo è perché siamo abituati ai numeri usuali. Con i moduli, non ci vuole nulla a sostituire un numero negativo con uno positivo! Per esempio, -4 è per definizione la stessa cosa che 12-4, cioè 8; quindi 5-4 è pari a 5+8, cioè 13 e quindi 1. All'atto pratico può ancora essere utile imparare a fare le differenze, visto che passare da 5-4 a 5+8 in realtà ci complica le cose: ma almeno in linea di principio la sottrazione è un'operazione inutile, e ci basta una tabellina dell'addizione e una lista dei numeri complementari.

Listato 1: opposti modulo 12

Moltiplicazione, ma soprattutto divisione!

Una tabellina per la somma è una cosa strana, ma nessuno si scandalizza nel caso della moltiplicazione: in fin dei conti, la buona vecchia tavola pitagorica la conosciamo tutti. La tabella 2 mostra appunto la moltiplicazione, stavolta modulo 10 per semplicità pratica: è come se guardassimo l'ultima cifra della tavola pitagorica standard. Alcune sue caratteristiche sono quelle a cui noi siamo abituati. La tabellina dello zero è sempre monotona: zero per un qualsiasi numero fa zero. Anche la tabellina dell'uno non è che sia poi così eccitante: uno per n fa n per ogni numero n. Negli altri casi, le cose cambiano eccome. A volte succede che due numeri diversi da zero, moltiplicati tra di loro, diano zero: lo vediamo nelle tabelline dei numeri pari e in quella del 5. Altre volte succede che nella tabellina tutti i numeri diversi sono presenti; lo vediamo, oltre che nella tabellina dell'uno, anche in quella di 3, 7 e 9. I due casi sono complementari: non è difficile dimostrare che o capita uno o l'altro, però sono buono e non lo faccio, visto che non è così importante nella nostra discussione. Qui ci basta vedere che 4*2 e 4*7 valgono entrambi 8, il che significa che nell'aritmetica modulare la divisione può avere più di un risultato, oppure non averne nessuno. Nel primo caso, 8/7 vale 2 oppure 7; nel secondo caso, 9/4 è impossibile, e non ce la facciamo nemmeno a pensare di estendere i numeri modulo 10 per avere un risultato fuori dall'insieme di partenza. Non abbiamo insomma l'equivalente dei numeri frazionari modulari, almeno così ad occhio.

 
Tabella 2: prodotto modulo 10                       Tabella 3: prodotto modulo 11

La situazione però cambia di colpo se stiamo usando l'aritmetica modulare con un modulo che è un numero primo. La tabella 3 mostra la tavola pitagorica per l'aritmetica modulo 11. In questo caso, a parte per lo zero, l'insieme dei multipli di ciascun numero è composto da tutti i numeri! Quindi ogni numero diverso da zero ha un suo inverso, che moltiplicato per il numero dato ci fa ottenere 1. Per i numeri modulo 11, l'inverso di 1 è 1, quello di 2 è 6, quello di 3 è 4, quello di 5 è 9, quello di 7 è 8, quello di 10 è 10. Come per la differenza, in questo caso possiamo permetterci il lusso di non imparare le divisioni; basta avere la tabellina per gli inversi, e così 5/8 (modulo 11) è uguale a 5*7 che vale 35 cioè 2.

Listato 2: inversi modulo 11

Potenze e logaritmi

Accenno solamente a quello che succede nel caso dell'elevazione a potenza e del logaritmo, limitandomi al caso in cui il modulo sia un numero primo dove le proprietà sono più interessanti: per fissare le idee, immaginiamo di usare i numeri modulo 11.

Tabella 4: potenze modulo 11

Scrivere a^b significa moltiplicare a*a*a... per b volte, sempre eliminando tutti i multipli di 11 nelle operazioni. Come nel caso dei numeri interi, definiamo a⁰ = 1 e a¹ = a. La tabella 4 è una "tavola potenziagorica": visto che l'elevazione a potenza non è commutativa e cioè a^b non è necessariamente uguale a b^a, preciso che la base si legge nella colonna a sinistra e l'esponente nella riga in alto. Notate nulla di strano? Dovrebbero esserci almeno due cose che saltano all'occhio. La prima è che la colonna della potenza 10 è composta da tutti 1; la seconda (in po' più difficile) è che alcune colonne (in lilla) e alcune righe (in azzurro) contengono tutti i numeri da 1 a 10. La prima di queste proprietà vale per l'aritmetica modulare quando il modulo è un numero primo p, ed è nota come Piccolo teorema di Fermat (no, non c'entra nulla con l'Ultimo teorema di Fermat se non che sono stati enunciati entrambi dal matematico e giudice francese). La seconda invece è vera per le colonne quando stiamo lavorando con l'aritmetica modulo p (primo) e prendiamo una potenza n tale che n e p-1 non abbiano fattori primi in comune; tecnicamente si dice che "n è primo con p-1". Per le righe, invece, i valori per cui vale la proprietà si chiamano generatori nella base p.

Per quanto riguarda le colonne lilla, possiamo dire che in quei casi è sempre possibile fare la radice n-sima di un numero, che ha sempre un solo valore (a meno di multipli del modulo). Non ditemi che è lo stesso con le radici cubiche "normali": anche lasciando perdere i valori complessi, ditemi voi qual è la radice cubica di 9! Per quanto ne so, comunque, questa proprietà non è poi così importante in pratica, a differenza di quella sui generatori. Se si sceglie una base che è un numero primo e un valore che è un generatore per questa base, infatti, è sempre possibile calcolarne il logaritmo discreto, che poi non è altro che il logaritmo in versione modulare. Se 2⁶ è congruo a 9 (modulo 11) questo significa che il logaritmo discreto di 9 in base 2 e modulo 11 vale 6. (Vale anche 16, 26, 36 e così via... ma anche in questo caso si prende convenzionalmente il più piccolo valore). La cosa interessante del logaritmo discreto è che non ci sono modi "facili" per calcolarlo, se non andando avanti a elevare a potenza la base finché non si trova il valore di cui ci serve il logaritmo. L'unico problema è che fare tutti questi conti costa, e il costo cresce esponenzialmente con la dimensione del modulo p. Questo significa che per un modulo abbastanza grande (il generatore può anche essere piccolo) abbiamo una "funzione trappola", che è facile da calcolare in un verso ma difficile da craccare nell'altro verso: situazione ideale per gli algoritmi a chiave pubblica, e infatti il protocollo Diffie-Hellman sfrutta i logaritmi discreti come base di un algoritmo di crittografia... algoritmo che non vi spiego in questa sede perché questa è matematica light.

Questo è tutto: come sempre domande e suggerimenti sono i benvenuti!

© Maurizio Codogno, 16 gennaio 2009
orna a .mau. — matematica — light