(la prima parte si trova qua)
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.

Tabella 2: prodotto modulo 10
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/4 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 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!

Ultimo aggiornamento: 2009-01-22 08:00