Supponete che qualche giorno prima della partita di andata dei quarti di finale della Champions League vi arrivi una email che dice “ho sviluppato un algoritmo che prevede correttamente i risultati sportivi. Per dimostrarGlielo, ecco quali sono le quattro squadre che passeranno alle semifinali:” e un elenco di quattro squadre. La mail termina con “per favore, non divulgate la notizia, per ovvie ragioni”. Voi non ci fate molto caso: quando però le partite si sono concluse, vi arriva una seconda email, che dice “Le quattro squadre che hanno passato il turno sono state proprio quelle da me previste. Perché Lei si possa sincerare della potenza dei miei algoritmi, Le dico quali saranno le finaliste”; e stavolta ci sono due nomi. Fate mente locale, vi ricordate che effettivamente l’interlocutore aveva ragione – e dire che non avreste scommesso un euro su una delle squadre – e aspettate incuriositi. Anche stavolta le predizioni si sono rivelate corrette: arriva una terza mail che dice “Se Lei vuole sapere il nome della squadra che vincerà la Champions League, invii cento euro a questo numero di conto corrente. Mi raccomando, però: non diffonda la notizia, altrimenti le quote crollerebbero.” Che fareste? Mandereste all’anonimo i soldi, pronti a scommetterne ben di più? Se avete risposto sì, forse è meglio che continuiate a leggere; altrimenti la lettura non sarà così importante ma spero sia comunque piacevole.
Il nostro anonimo interlocutore aveva infatti iniziato a spedire 128.000 email – tanto non gli costava nulla – divise in sedici gruppi, ciascuno dei quali aveva una quaterna diversa di semifinaliste previste. Una volta visti i risultati, il secondo gruppo di spedizioni è stato fatto solo agli 8000 destinatari che avevano ricevuto la predizione corretta (suppongo che le probabilità che passi il turno una squadra oppure l’altra siano le stesse, ma il ragionamento vale lo stesso); il terzo messaggio con la richiesta di denaro, infine, solo ai 2000 per cui anche i risultati delle semifinali erano stati previsti correttamente. La maggior parte delle persone ha ricevuto solo la prima mail con le previsioni errate, ma voi eravate tra i duemila “fortunati”, e con buona probabilità sgancerete al nostro ignoto amico cento euro per un’ulteriore predizione assolutamente casuale. Se anche solo la metà dei polli ci casca, sono 100000 euro in saccoccia senza troppa fatica: niente male, vero?
Purtroppo l’evoluzione non ha insegnato a noi umani come trattare le probabilità, soprattutto le probabilità a posteriori. Quello dell’esempio è un caso limite: prima dell’invio della prima email avete una possibilità su 64 di ricevere tutti e sei i risultati corretti, e quando vi arriva la lettera con la richiesta di un piccolo contributo tendete a pensare ancora a quella probabilità, mentre quella a posteriori è ovviamente la certezza nel vostro caso (e l’impossibilità negli altri 63 casi… la probabilità è come l’energia, nulla si crea e nulla si distrugge). Ma ci sono anche altri casi in cui le probabilità a posteriori sono sovrastimate e non sottostimate. Il caso classico che viene fatto è quello del test per l’Aids. Supponiamo che il test rapido abbia una probabilità su 100 di dare un falso positivo (una persona sana che risulti aver contratto l’infezione), e che il vostro stile di vita assai morigerato sia tale che a priori avete una possibilità su 1000 di essere infetti. Andate a fare il test, e vi richiamano dicendo che il test rapido è risultato positivo e quindi occorre sottoporvi a un test più accurato. Quant’è la probabilità a posteriori (cioè dopo la positività al test rapido) che voi siate effettivamente infetti? il 99%? No, è molto meno. Su un milione di persone con il vostro stile di vita, infatti, solo 1000 sono statisticamente infette. Il test darà risultato positivo su questi 1000 e sull’1% degli altri 999000, cioè su 9990 persone (che arrotondo a 10000 per fare meglio i conti). Quindi ci sono 1000 infetti su quasi 11000 positivi all’esame, pari a meno del 9%. In altre parole: c’è da preoccuparsi (siamo passati da una probabilitàa priori dello 0,1% a quasi il 9%) ma non avete ancora un piede e mezzo nella fossa!
Tutti questi conti sono ben noti da secoli ai matematici, e la formula che calcola le probabilità a posteriori a partire da quelle a priori e dai risultati si chiama Teorema di Bayes. Il fatto che sia ben nota non cambia però le carte in tavola: continua a risultare poco intuitiva, e quindi anche persone con una buona conoscenza scientifica ci possono cascare.
C’è anche un altro fenomeno relativo alle probabilità che fa prendere lucciole per lanterne, anche se più che matematico è probabilmente di natura psicologica, ed è l’aggiustamento probabilistico a posteriori. Inizio con un esempio che di matematico non ha nulla: le centurie di Nostradamus. Adesso non sono molto di moda, ma negli anni ’70 del secolo scorso c’erano vari studiosi che invariabilmente mostravano come Nostradamus avesse previsto i vari fatti accaduti: una volta verificatisi tali fatti, i riferimenti nel testo del veggente erano infatti inequivocabilmente chiari. Purtroppo le previsioni per il futuro non sono mai state così chiare, un po’ come quelle degli astrologi: o magari è tutto un complotto delle società di assicurazione che non vogliono finire in rovina, e quindi stanno attente a eliminare tutti i possibili metodi per conoscere davveo il futuro.
Spostandoci ìn un ambito piu matematico ancorché qualitativo, prendo un esempio purtroppo tragico: il terremoto abruzzese di questi giorni, e la coda di polemiche perché le previsioni di Gioacchino Giampiero Giuliani non sono state tenute in considerazione. Guardiamo le cose da un punto di vista strettamente matematico. La probabilità a priori che ci sia un terremoto di intensità distruttiva in un giorno specifico in una zona specifica (diciamo con l’epicentro in un raggio di quindici km da un punto indicato) è molto bassa, per fortuna: e lo è anche se ci si trova in una zona sismica, e comincia a diventare significativo – ma non ancora elevato, sempre per fortuna – in presenza di alcuni segnali. Immaginiamo che Giuliani avesse effettivamente previsto il terremoto del 6 aprile all’Aquila, ma non avesse detto nulla perché in fin dei conti era già sotto inchiesta per procurato allarme. Resta il fatto che il 28 marzo aveva affermato che il terremoto sarebbe stato il giorno successivo (sette giorni prima della data effettiva) a Sulmona (cinquanta chilometri in linea d’aria dall’Aquila). Chi dice “ci aveva azzeccato” è come chi pensa di aver vinto alla lotteria perché la differenza tra il numero del suo biglietto e quello vincente è solo 14: non esattamente un gran risultato. Eppure, proprio perché l’evento è così raro e distruttivo, si pensa inconsciamente che un’approssimazione di questo tipo sia accettabile. Visto che non possiamo riprodurre a piacere i terremoti, non abbiamo un modo di valutare aprioristicamente la probabilità che da una serie di segnali si giunga a un sisma. D’altra parte, mentre in linea di principio ha senso avere qualche allarme a vuoto, non possiamo nemmeno averne troppi; non tanto per l’effetto “al lupo al lupo”, quanto per gli ovvi problemi organizzativi.
La morale di tutto questo è semplice: fate sempre attenzione quando valutate delle probabilità, e non fidatevi degli argomenti spannometrici!

Ultimo aggiornamento: 2009-04-11 07:00

Probabilmente la vignetta di oggi di Ferd’nand non vi farà molto ridere, soprattutto se la vostra abilità nei lavori manuali è comparabile con la mia. La striscia però rappresenta visivamente un importante fatto geometrico, che probabilmente è passato del tutto inosservato a scuola.
Una delle informazioni generalmente inutili che rimangono appiccicate dagli anni scolastici è “per due punti passa una retta”. La frase corretta, sottintendendo che si parla del piano euclideo, è “per due punti passa una e una sola retta”, ed è uno dei postulati degli Elementi di Euclide, vale a dire un’affermazione che si deve prendere per vera senza cercare di dimostrarla. Se i punti presi sul piano sono tre, bisogna essere fortunati per averli tutti sulla stessa retta; in genere non capita. Sì, ci sarebbe la battuta “per tre punti passa una retta, purché sufficientemente spessa”, ma non divaghiamo… L’affermazione si può anche leggere alla rovescia: dati due punti, abbiamo definito una retta ben specifica.
Se dal piano passiamo allo spazio, però, le cose si fanno più interessanti. Il postulato equivalente a quello indicato qui sopra dice “per tre punti passa uno e un solo piano”, o se preferite “dati tre punti, abbiamo definito un piano”. Come nel caso del piano aggiungere un terzo punto non permette più di essere certi di avere una retta che passi per tutti e tre i punti, così quattro punti nello spazio possono non appartenere a nessun singolo piano, come il nostro Ferd’nand si è accorto col suo tavolino che balla. Ma se il tavolino ha solamente tre gambe, la stabilità è assicurata! Naturalmente non è detto che le cose posate sul tavolino non scivolino a terra, o detto in altro modo il piano del tavolino non è detto sia parallelo al pavimento (o meglio, come fa correttamente notare S. nei commenti, e perpendicolare alla forza di gravità: un tavolino parallelo a una ripida strada di San Francisco sarebbe scarsamente utile); ma è comunque qualcosa. Questo tra l’altro è il motivo per cui si usano i treppiedi e non i quadripiedi, se si deve fare una fotografia e si vuole che la macchina fotografica sia stabile. Insomma, anche la geometria ha la sua utilità

Ultimo aggiornamento: 2009-04-08 10:38

Ho trascorso la pausa pranzo andando al Poli a sentire la conferenza “Modelli matematici e crisi finanziaria”, nell’ambito dei Seminari di Cultura Matematica del dipartimento di Ingegneria Matematica. Sì, lo so che ho appena scritto un ossimoro.
Premetto che io di matematica ne capisco abbastanza, di statistica un po’ e di economia nulla, e aggiungo che sono riuscito a resettare il mio palmare prima di salvare gli appunti che mi ero preso, quindi può darsi che io abbia preso delle cantonate: tanto ci sono fior di economisti tra i miei ventun lettori, che saranno lesti a correggere. La netta sensazione che però ho avuto è che il sistema bancario prenda gli strumenti matematici e poi li usi in maniera tale che i fisici in confronto sono dei formalisti puri.
Innanzitutto c’è il leverage, vale a dire quanti soldi la banca dà in giro rispetto al suo capitale (troppi, soprattutto negli ultimi anni…), ma questo con la matematica c’entra poco. Più interessante il racconto di Emilio Barucci su come funzionano le cartolarizzazioni dei mutui casa. Se un mutuatario ha probabilità x di non poter pagare, con varianza σ², basta prendere mille mutuatari e mettere insieme i loro mutui. Se le loro probabilità di default sono indipendenti, un po’ come quando si lancia un dado N volte, la probabilità di default del pacchettone continua ad essere x, ma la varianza scende a σ²/1000, il che mi torna: se provate a disegnare la distribuzione binomiale di dieci oppure diecimila lanci di moneta nella stessa scala, vedrete che la seconda sembra una gaussiana molto più stretta. A questo punto si prende il pacchetto dei mille mutui e si fanno delle quote: non però uguali, ma dividendolo in tranche. In pratica ci sono le quote più rischiose, che però quando le cose vanno bene danno tanti soldi, e quelle via via più sicure, con rating che arrivava anche ad AAA (cioè una possibilità su 20000 di diventare carta straccia entro un anno). Queste quote sicure sono state vendute come obbligazioni sul mercato: solo che le banche americane, invece che fare come da noi dove le obbligazioni venivano rifilate agli utenti finali, se le compravano tra loro, spostando le voci nel bilancio ma rimanendo comunque fregate con una crisi come questa.
Ma anche questo non c’entra con la matematica light, se non per un punto fondamentale: la varianza si riduce così tanto solo se i vari mutui sono statisticamente indipendenti. Nel caso ci sia correlazione perfetta, la varianza rimane ovviamente σ²; altrimenti ci sarà un valore intermedio. Cosa facevano allora quelli che erano incaricati di suddividere il pacchetto dei mutui nelle varie tranche? Semplice: giocavano con i parametri, e soprattutto con la correlazione tra i mutui, per trovare i risultati che gli andassero bene. Un po’ insomma come i “sondaggi televisivi” dove facciamo una domanda a una decina di persone e mostriamo le tre risposte che ci piacciono di più.
Ma il secondo punto “molto matematico” è quello del Valore a rischio, o VaR. Questo numeretto misurerebbe qual è il valore minimo che ci aspettiamo il nostro portafoglio avrà in una certa data nel 95% dei casi: in pratica nel 5% dei casi scenderemo sotto quel valore, nel 95% invece lo supereremo. In condizioni perfette – leggasi, distribuzione del rischio sotto forma di gaussiana pura – il VaR è un’ottima misura del rischio. Peccato che non solo le condizioni non sono generalmente perfette, ma è anzi vantaggioso mettere investimenti molto più rischiosi in quel 5%, visto che al mondo sono nascosti (il VaR resta lo stesso) ma si può guadagnare di più… se le cose vanno bene, naturalmente.
Insomma, il concetto di base mi pare essere “prendiamo le formulette matematiche, e facciamo finta funzionino sempre; se non funzionano, cominciamo a spostare i numerini fino a che non dicono quello che vogliamo noi”. Belle cose, e poi uno si stupisce che stia andando tutto a catafascio!

Ultimo aggiornamento: 2009-03-18 15:05

Nella rubrica odierna di Lessico e Nuvole, Stefano Bartezzaghi parla di una ipotetica operazione da aggiungere alle quattro usuali: l’unisione, che «sarebbe l’operazione per cui due uniso due fa ventidue», o per meglio specificare “due uniso tre fa ventitré”.
Tralasciamo il fatto che l’unisione si fa evidentemente in una base specifica, nel nostro caso in base 10, e veniamo alla sua operazione inversa. Secondo Stefano, l’unisione sarebbe un’operazione autoinversa, tale cioè che ventidue uniso due fa due. Io non sono d’accordo; secondo me ventidue uniso due fa duecentoventidue. Propongo come operazione inversa dell’unisione la stacchisione, tale per cui ventitrè stacchiso tre fa due (e ventitré stacchiso due fa tre…)
Voi che ne pensate, sia riguardo alla nomenclatura che all’operazione in sé?

Ultimo aggiornamento: 2009-03-16 09:21

[Questo è un vero articolo di matematica light, nel senso che ho eliminato equazioni e dimostrazioni. Chi volesse fare le cose un po’ più sul serio, può andare a leggere la versione completa su una Prestigiosa Rivista Matematica]
Immagino che abbiate già sentito parlare del Triangolo di Tartaglia, magari sotto il nome di Triangolo di Pascal. È un triangolo (ma vah?) infinito, che ha in punta e sui due lati tutti 1; gli altri numeri si calcolano sommando i due numeri immediatamente al di sopra. Il triangolo di Tartaglia, come tante strutture matematiche, spunta da tante parti; ad esempio, i coefficienti dello sviluppo binomiale (1+a)ⁿ sono proprio gli elementi della riga n del triangolo di Tartaglia. Ah: la prima riga, quella per intenderci dove si trova solo il numero 1, è la “riga zero”. I matematici amano partire da zero.
Oltre alla formula ricorsiva per ricavare i numeri del triangolo di Tartaglia, ce n’è anche una che permette di calcolare esplicitamente il k-simo elemento della n-sima riga; esso vale n!(k!(n–k)!), dove l’esclamativo indica la funzione fattoriale. Ah, il primo elemento, quello per intenderci più a sinistra, è l'”elemento zero”. Vi ho già detto che i matematici amano partire da zero?
Ma immaginiamo che non ci interessi sapere il valore esatto dei vari elementi del triangolo di Tartaglia, ma solo se sono pari o dispari. Proviamo a disegnare il triangolo mettendo un pixel nero se il numero è dispari e uno bianco se è pari: il risultato, come vedete, sembra una specie di merletto e ha l’aspetto di tipo frattale. In effetti la figura limite è nota come Triangolo di Sierpinski: se siete romantici, potete anche vederla così. Spesso i frattali hanno una descrizione semplice, e anche in questo caso in effetti c’è un modo per trovare rapidamente se un pixel è bianco o nero, cioè se il numero corrispondente è pari o dispari. Guardando la figura, vediamo che ci sono delle righe tutte nere, altre righe quasi tutte bianche, e ancora altre righe un po’ alternate, il che però non ci dice molto; la spannometria è utile, ma in questo caso non ci basta.
Il matematico che scoprì la regola è un poco conosciuto francese vissuto nell’Ottocento: Edouard Lucas. Lucas è forse più noto ai matematici ricreativi che a quelli accademici, anche se il test che permette di annunciare ogni tanto la scoperta di un numero primo enorme è stato inventato da lui e poi affinato da Lehmer. Non è un caso che il test di primalità valga per i numeri della forma 2ⁿ-1: Lucas era affascinato dai numeri scritti in notazione binaria, e purtroppo per lui era nato con un secolo di anticipo, perché altrimenti sarebbe stato deliziato dagli elaboratori elettronici che in base 2 ci lavorano. Un altro esempio di questa sua infatuazione è la creazione del gioco della Torre di Hanoi, nella cui soluzione le potenze di due giocano un ruolo fondamentale.
Torniamo al nostro triangolo, e prendiamo un elemento a caso; quello in posizione k nella riga n, ricordandoci sempre che si inizia a contare da zero. Scriviamo ora k e n in formato binario, e mettiamoli uno sotto l’altro, aggiungendo se necessario degli zeri a sinistra di k perché siano della stessa lunghezza. Cerchiamo ora tutti i bit di k che hanno valore 1 e vediamo il bit corrispondente di n; se per ciascuno di quei bit di k anche quello corrispondente di n vale 1, allora il nostro elemento sarà dispari, altrimenti sarà pari. Lo so, detto così è incomprensibile; quindi faccio un esempio pratico. Se n vale 19, cioè 10011 in notazione binaria, ci saranno esattamente otto valori di k per cui l’elemento del triangolo sarà dispari: quelli della forma x00xx, dove x può valere 0 oppure 1. Andando a scalare, ci saranno così 10011 in formato binario, cioè 19; 10010=18, 10001=17, 10000=16, 00011=3, 00010=2, 00001=1, e… 00000=0. Quest’ultimo risultato può sembrare un po’ strano: in fin dei conti non ci sono mica bit di k che valgano 1, e quindi si direbbe che l’ipotesi non valga. Ma i matematici amano parlare delle mirabolanti proprietà dell’insieme vuoto: se ci pensate, questo caso è la stessa cosa che dire “se non faccio, non sbaglio”. Poi dovreste fidarvi, visto che l’elemento in posizione zero è il primo della riga (vi ho già detto che i matematici amano partire da zero?) e quello vale sicuramente 1.
Vi faccio ancora qualche esempio facile. Le righe 2, 4, 8, 16… del triangolo, vale a dire la terza, la quinta, la nona… sono quelle dove gli unici pixel neri sono i due estremi, dove cioè k = 0 e k = n; in effetti n è della forma 1000…000 e non si può fare molto. In compenso, le righe appena sopra di esse, cioè la 1, 3, 7, 15, … sono completamente nere, e in effetti se n è della forma 1111…111 si può scegliere un k qualsiasi, perché tanto i bit sopra sono tutti a 1. Se ci si pensa un po’ su, si può capire perché ci siano i triangoli bianchi che man mano si riducono (aiutino: dipende da quanti 1 ci sono a destra nella rappresentazione binaria di k); ma si può anche lasciar perdere tutto questo e limitarsi ad apprezzare il risultato. Qui si vuole essere light, in fin dei conti!

Ultimo aggiornamento: 2014-03-05 11:05

C’è una rubrica su Mathematics Magazine della MAA che si chiama “Proofs without Words”, e che appunto presenta dimostrazioni per così dire visive: non sono vere dimostrazioni, naturalmente, ma chiunque sia abituato a fare un po’ di matematica, dopo aver visto il disegno, sa esattamente quali sono i passi formali da fare per una dimostrazione, mentre chi abituato non è riesce comunque a convincersi.
La cosa mi è venuta in mente ieri, dopo avere scoperto che qualcuno era finito sul mio blog con la chiave di ricerca «in un triangolo rettangolo la mediana relativa all ipotenusa è congruente a metta ipotenusa-dimostrazione di questa teorema». Il teorema mi ricordava qualcosa, ma non ricordavo esattamente cosa: ho preso carta e penna per vedere la dimostrazione, e in un attimo è uscito fuori questo disegnino (non cliccateci sopra se volete prima dimostrarvelo da voi). Non è carino?

Ultimo aggiornamento: 2009-02-24 07:00

(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

L’aritmetica modulare è una di quelle parti della matematica che non sono affatto difficili da comprendere, e anzi vengono usate nella vita di tutti i giorni senza grandi problemi, però non vengono quasi mai insegnate a scuola. Provo così a scrivere qualcosa al riguardo, per la gioia di grandi e piccini.
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
(continua)

Ultimo aggiornamento: 2009-01-19 08:00