Sono poche le persone a cui piace la matematica.

Questo fatto del mondo è talmente onnipresente nella nostra quotidianità che non necessita nemmeno di studi statistici per supportarlo. Semplicemente, è così, e noi tutti ne siamo consapevoli.

Se ci si ferma a riflettere sul modo in cui viene insegnata la matematica, ciò non dovrebbe sorprendere più di tanto.

Non lo dico semplicemente per fare polemica, ma sono dell’opinione che il ruolo del tradizionale ciclo di studi – composto da elementari, medie e superiori – almeno per come si realizza in pratica, non è assolutamente quello di insegnare ed educare i giovani di oggi al fine di prepararli alle difficoltà della vita di domani.

Rimuovendo casi eccezionali di professori encomiabili, ed utilizzando esclusivamente la mia esperienza personale, le superiori, nella mia vita, sono esistite principalmente per:

  • pagare qualche stipendio.

  • dare l’idea di educare.

  • far sprecare tempo, sia agli studenti, che ai professori e al personale scolastico.

Detto questo, mi fermerò qui con queste divagazioni per entrare direttamente nel tema del blog post.

In questo blog post, come in tutto ciò che scrivo e ciò che faccio, voglio essere pragmatico. Come al solito, il mio obiettivo è descrivere nel modo più semplice possibile a mia disposizione ciò che imparo vivendo, amando, e soffrendo.

L’idea, in particolare, è quella di descrivere le poche ma importanti cose che ho imparato sull’essenza della matematica, con la speranza di far crollare qualche certezza a chi pensa di non essere portato minimamente per questa materia, tanto bella quanto, purtroppo, tremendamente incompresa.

Buona lettura.

Table of Contents⌗

La maggior parte delle persone, dopo aver provato sulla propria pelle il ciclo di studi tradizionali, associano inevitabilmente la matematica alla mera memorizzazione di formule astruse e apparentemente distaccate dalla vera realtà di tutti i giorni.

Che senso ha ricordare a memoria la formula – riportata a seguire con il solo intento di far rivivere qualche ricordo traumatizzante al lettore – per fattorizzare un polinomio di secondo grado?

\[x_{1, 2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]

In realtà, non serve proprio a niente la semplice memorizzazione. La matematica, quella concreta e utile, non è questo e non serve a questo.

Sono i computers quelli bravi a ricordare e a fare i calcoli velocemente, non gli esseri umani!

Qual è la nostra forza quindi? Cosa ha l’essere umano che la macchina, ancora, non riesce ad avere? Creatività. Intuizione. Ingegnosità. Saper ragionare in modo creativo per risolvere un problema utilizzando approcci nuovi e mai tentati prima. Queste sono le nostre forze, ed è questo il vero potere di ogni matematico:

saper manipolare concetti astratti al fine di risolvere problemi concreti.

Queste abilità non sono utili solo ai matematici. Non dobbiamo lasciare solo a loro l’enorme ricchezza contenuta nella matematica e in tutte le sue applicazioni, di cui il computer digitale moderno è l’esempio perfetto.

La matematica è uno strumento imprescindibile per tutti, anche, e specialmente, per un informatico.

I linguaggi della matematica⌗

Chi vuole conoscere le macchine in profondità deve cambiare fin da subito la propria concezione della matematica.

Lo ripeto: la matematica non ha nulla a che fare con l’imparare qualche formula a memoria, o risolvere degli esercizi ripetendo gli stessi passi visti a lezione.

Questa visione è una distorsione della realtà, ed è una vera tristezza riconoscere che questa è l’unica visione della matematica offerta dalla maggior parte del sistema educativo, che tipicamente solo all’università, e solo per pochi fortunati, ha l’occasione di essere estesa e integrata per racchiudere al suo interno la vera essenza della matematica.

Ma che cos’è la matematica?

Non ritengo di essere abbastanza competente per poter rispondere in modo soddisfacente a tale domanda. Credo però di poter dare uno spunto di riflessione, che potrebbe aiutare a capire cosa tratta effettivamente questa materia.

La matematica è, in ultima analisi, un insieme di linguaggi.

Ogni linguaggio ha le proprie caratteristiche e il proprio modo di modellare il mondo.

C’è un linguaggio per la geometria – che sfrutta maggiormente l’abilità di visualizzazione del cervello umano – uno per l’aritmetica e uno per l’algebra – entrambi dei quali, invece, sono più simbolici e utilizzano l’abilità del cervello di processare il linguaggio tramite dei simboli.

Sono tantissimi i linguaggi della matematica. Giusto per menzionarne un po’: la crittografia, la topologia, l’analisi matematica, le equazioni differenziali, l’analisi complessa, la probabilità, la statistica, la teoria dei grafi, la teoria dei gruppi, la teoria delle categorie, la teoria dei tipi, e via dicendo…

Imparare a pensare in modo matematico significa imparare alcuni di questi linguaggi, a seconda delle proprie necessità, in modo da poterli poi utilizzare per analizzare e risolvere i problemi in cui ci imbattiamo nel mondo reale.

Quali conseguenze possiamo trarre da questa semplice, e decisamente approssimata, ma comunque valida, caratterizzazione della matematica?

Come prima cosa, osserviamo come parlare di “matematica” è molto simile al parlare del nulla. Questo termine infatti è troppo vago e troppo ambiguo. Sono così tanti, e così diversi tra loro i linguaggi contenuti sotto questo termine, che risulta estremamente limitativo parlare in senso generale di matematica.

Posso capire il perché classifichiamo tutti questi linguaggi diversi sotto uno stesso nome, specialmente pensando a coloro che sanno poco e niente di queste cose. D’altronde è necessario ammettere che comunque, anche se sono abbastanza diversi una volta approfonditi un minimo, i linguaggi della matematica condividono molte cose, come ad esempio lo stesso approccio logico-astratto.

Eppure, questo primo fatto ha una interessante conseguenza.

Se i linguaggi della matematica sono così diversi l’uno con l’altro, perché tipicamente noi ci limitiamo a dire frasi come: “sono scarso in matematica”, oppure “non mi piace la matematica” ? Perché invece non entriamo nel dettaglio, per capire esattamente quali sono le nostre forze? Perché non diciamo piuttosto: “ho serie difficoltà a visualizzare forme geometriche, ma sono piuttosto bravo nella manipolazione di formule algebriche”?

Da quello che sento e vedo in giro, molto spesso ho la sensazione che le persone associano la matematica unicamente all’aritmetica, uno dei primi linguaggi matematici scoperti. In particolare associano la matematica alla procedura di eseguire dei calcoli aritmetici

Il modello mentale di queste persone è il seguente:

  • Se sei bravo in matematica, allora sai eseguire calcoli complessi in modo abbastanza veloce.

  • Viceversa, se sei bravo ad eseguire calcoli complessi allora sei portato per la matematica.

Se invece consideriamo le rispettive affermazioni negative (i contrappositivi, se vogliamo essere tecnici), otteniamo le seguenti affermazioni, equivalenti a quelle di prima:

  • Se non sei bravo ad eseguire calcoli complessi in modo abbastanza veloce, allora non sei portato per la matematica.

  • Se non sei portato per la matematica, allora sei lento a calcolare.

In formula,

\[\text{Matematica} \iff \text{Calcolo aritmetico}\]

Sono tante le cose che si perdono in questa tremenda semplificazione. E non sto parlando solamente di voti in classe. Sto parlando di passioni, opportunità e lavori. Sto parlando di potenziali vite passate nella gioia di studiare e condividere qualche specifico linguaggio della matematica.

Tutte cose perse nel momento in cui dimentichiamo la complessità della questione, e ci limitiamo a dire, spinti principalmente dalla nostra ignoranza e, a mio avviso, anche da una profonda voglia di condividere una stessa incapacità: “non fa per me”, “non sono portato per queste cose”.

Un tempo anche io pensavo di non essere in grado di studiare una materia come la matematica. Poi, all’università, dopo tanto impegno, ho capito che sono perfettamente in grado di parlare alcuni dei linguaggi della matematica.

Detto questo, tutt’ora mi ritengo una frana nell’effettuare dei calcoli aritmetici mentalmente. Anche quelli più semplici mi richiedono più tempo della media.

Per mia fortuna però ho imparato a capire la differenza tra le due cose.

La matematica discreta⌗

Tra i tanti linguaggi della matematica, quello principale a cui è interessato un informatico prende il nome di matematica discreta.

Nel contesto matematico l’aggettivo “discreto” indica il fatto che questo tipo di matematica studia oggetti che possono essere contati – in gergo tecnico enumerati – tramite i numeri naturali, che sono i numeri che tipicamente utilizzamo per contare, ovvero

\[0, \;\; 1, \;\; 2, \;\; 3, \;\; 4, \;\; 5, \;\; 6, \;\; \ldots\]

Osservazione 1: Molti linguaggi della matematica condividono delle forme di scrittura che non si trovano in altri linguaggi del sapere umano.

Per fare un esempio particolare, quando si fa matematica, qualsiasi tipo di matematica, con i tre puntini \(\ldots\) tipicamente si indica il fatto che la sequenza che si stava scrivendo continua in avanti con la stessa regola di aggiornamento, dove la regola di aggiornamento è la regola che ci permette di passare da un elemento della sequenza all’elemento successivo.

Nel caso della sequenza in alto, la regola di aggiornamento era semplicemente quella di aggiungere \(1\) all’elemento, in quanto

\[0 \overset{+ 1}{\longrightarrow} 1 \overset{+ 1}{\longrightarrow} 2 \overset{+ 1}{\longrightarrow} 3 \overset{+ 1}{\longrightarrow} 4 \overset{+ 1}{\longrightarrow} 5 \overset{+ 1}{\longrightarrow} 6 \overset{+ 1}{\longrightarrow} \ldots\]

Dato che risulta impossibile scrivere tutti i numeri naturali (sono infiniti, dopo tutto), tipicamente si scrivono solamente i primi numeri della sequenza; la restante parte può essere ottenuta applicando la regola di aggiornamento quante volte si vuole.

Ora, il caso vuole che i matematici sono fin troppo spesso pigri, e dunque molte volte la regola di aggiornamento non è esplicitamente definita, come del resto io stesso non ho esplicitato quel \(+1\) la prima volta che ho scritto la sequenza in alto.

Bisogna quindi stare molto attenti quando si ha a che fare con questo tipo di notazione \((\ldots)\): potremmo pensare di aver capito la regola di aggiornamento, quando in realtà la vera regola è completamente diversa.

I numeri naturali formano un insieme, che intuitivamente può essere immaginato come un sacco contenente vari oggetti.

Possiamo considerare insiemi dei più svariati oggetti, come ad esempio l’insieme delle persone umane, o l’insieme delle persone umane che vogliono diventare hackers, o ancora l’insieme delle persone umane che vogliono diventare hackers e che sono disposte a sudare e studiare per raggiungere tale obiettivo.

Secondo voi come sono organizzati questi insiemi, qual è il più grande, e quale il più piccolo?

Nel caso dell’insieme dei numeri naturali, abbiamo un insieme i cui elementi sono, appunto, i vari numeri naturali. Dato che questo insieme è molto comune, è stato introdotto il simbolo \(\mathbb{N}\) per indicarlo. Troviamo quindi la seguente notazione

\[\mathbb{N} = \{0, \;\; 1, \;\; 2, \;\; 3, \;\; 4, \;\; 5, \;\; 6, \;\; \ldots \}\]

Dove le parantesi graffe \(\{, \}\) indicano il fatto che stiamo definendo un insieme, mentre le virgole sono utilizzate per separare i vari elementi dell’insieme.

Osservazione 2: La difficoltà nell’imparare bene i linguaggi della matematica è anche dovuta al fatto che molto spesso questi linguaggi contengono, sorprendentemente, un sacco di convenzioni e di scelte abbastanza arbitrarie.

Un esempio concreto di questo può essere trovato nella definizione dei numeri naturali. Oltre all’utilizzo estremamente poco formale della parola “naturali”, che fa sempre venire in mente la potente citazione di Leopold Kronecker, un matematico vissuto nel 1800,

Dio fece i numeri naturali; tutto il resto è opera dell’uomo.

Leopold Kronecker.

sui numeri naturali va avanti un dibattito forse destinato a non essere mai del tutto risolto: lo \(0\) fa parte dei numeri naturali? In formula,

\[0 \in \mathbb{N}?\]

Dove \(\in\) è il simbolo che rappresenta il concetto di “appartenenza di un elemento ad un insieme”.

Questa domanda non ha una chiara risposta. L’unica cosa che possiamo dire è che dipende. Dipende dal contesto matematico in cui ci troviamo. Dipende dalle persone con cui stiamo interagendo. Semplicemente, dipende.

Ebbene sì: la matematica non è poi così assoluta e fredda come può sembrare inizialmente. C’è molto calore umano in queste scelte arbitrarie, confuse e molto spesso tremendamente soggettive.

Io personalmente considero sempre lo \(0\) come un numero naturale, ma ammetto anche che la mia scelta non si basa su qualche ragionamento filosofico da esporre. Semplicemente, la mia intuizione mi porta a condividere il pensiero del mio professore di matematica discreta all’università, che diceva sempre che lo \(0\) è un numero naturale, perché quando si conta, si inizia sempre da \(0\), ovvero dal nulla.

Questa diatriba, tra l’altro, è molto simile a quella presente nei linguaggi di programmazione per quanto riguarda l’indicizzazione degli array o delle liste. Nella maggior partei dei linguaggi, tipo il C, gli indici partono da \(0\).

int array[]      = {5, 6, 7};

printf("The first value is: %d\n", array[0]);   // 5
printf("The second value is: %d\n", array[1]);  // 6
printf("The third value is: %d\n", array[2]);   // 7

In altri (pochi) linguaggi, invece gli array vengono indicizzati partendo da \(1\).

Voglio adesso introdurre un argomento, l’aritmetica modulare, che a prima vista potrebbe sembrare una divertente divagazione matematica, ma che in realtà è oramai diventata uno strumento fondamentale della crittografia.

La crittografica, per chi non conoscesse nulla al riguardo, è quell’attività umana volta al proteggere le informazioni scambiate tra due o più individui.

Detto altrimenti, la crittografia cerca tecniche per risolvere i seguenti problemi:

  • Come mi assicuro che un certo messaggio possa essere letto solamente dal legittimo destinatario, e non da altre persone?

  • Come mi assicuro che il contenuto di un messaggio non possa essere modificato da terze parti?

L’aritmetica modulare⌗

L’aritmetica modulare è una tipologia di aritmetica che ha svariati utilizzi sia nell’informatica in generale, che nella crittografia nello specifico.

Dato che i moderi calcolatori lavorano con una quantità finita di memoria, i sistemi crittografici implementati su questi calcolatori devono anch’essi necessariamente utilizzare una quantità finita di memoria.

Da qui nasce il grande utilizzo dell’aritmetica modulare: questa tipologia di aritmetica infatti ci permette di lavorare con degli insiemi di elementi finiti.

Per chi fosse interessato a vedere in pratica come si può utilizzare la conoscenza di queste cose matematiche per rompere un sistema crittografico, consiglio vivamente la visione del seguente video presente sul mio canale youtube

Nell’aritmetica tradizionale l’insieme degli elementi preso in considerazione è l’insieme dei numeri naturali

\[\mathbb{N} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \ldots\}\]

o, eventualmente, l’insieme degli interi, che è l’insieme dei naturali positivi a cui però si aggiungono anche i numeri negativi

\[\mathbb{Z} = \{0, 1, -1, 2, -2, 3, -3, \ldots\}\]

Quando lavoriamo nel contesto dell’aritmetica modulare invece abbiamo sempre un insieme finito di elementi. Per denotare questo insieme si utilizza la seguente notazione:

\[\mathbb{Z}_n = \{0, 1, \ldots, n-1\}\]

Il valore \(n\) è detto modulo e stabilisce la particolare aritmetica con cui vogliamo lavorare. Abbiamo una aritmetica diversa per ogni valore di \(n \in \mathbb{N}^+\).

Esempi:

  • Se \(n = 3\), allora lavoriamo in modulo \(3\) con i seguenti elementi

    \[\mathbb{Z}_3 = \{0, 1, 2\}\]

  • Se \(n = 10\), allora si lavora modulo \(10\), e gli elementi sono così descritti

    \[\mathbb{Z}_{10} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\]

Il ruolo dei simboli⌗

Dato che abbiamo un insieme di elementi finito, le operazioni tradizionali di somma \((+)\), sottrazione \((-)\), prodotto \((\cdot)\) e divisione \((/)\) sono leggermente modificate rispetto a quelle che conosciamo dalle scuole elementari.

Concentriamoci in questo blog post su come funzionano la somma e il prodotto quando lavoriamo in un contesto modulare. La sottrazione viene trattata in modo analogo alla somma, ma la tralasciamo per non inserire dettagli inutili. Per quanto riguarda la divisione invece, ci sono varie cose da tenere in considerazione, e quindi verrà lasciata fuori per non rendere il tutto troppo complicato.

Nell’aritmetica tradizionale che abbiamo imparato alle elementari abbiamo che, ad esempio

\[2 + 3 = 5\]

Ma cosa succede se sommiamo \(2\) a \(3\) quando lavoriamo in una aritmetica modulo \(3\), ovvero in \(\mathbb{Z}_3\)? Notiamo che qui il problema sta proprio nel fatto che il numero \(5\) non è un elemento di \(\mathbb{Z}_3\), dato che, come avevamo già detto prima, \(\mathbb{Z}_3\) contiene solamente i seguenti elementi

\[\mathbb{Z}_3 = \{0, 1, 2\}\]

L’idea è quella di modificare le tradizionali operazioni aritmetiche (che sono appunto somma, prodotto, divisione e sottrazione) per ottenere sempre numeri all’interno dell’insieme con cui stiamo lavorando. In questo caso \(\mathbb{Z}_3\).

A tale fine si utilizza il concetto di resto.

Ricordiamo, in particolare, che quando dividiamo un numero intero, tipo \(5\), per un altro numero intero, tipo \(3\), il primo potrebbe non essere un multiplo del secondo. In altre parole, abbiamo una divisione con resto. Se dividiamo \(5\) e \(3\), ad esempio, abbiamo una divisione con quoziente \(1\) e resto \(2\), proprio perché

\[\underbrace{5}_{\text{dividendo}} = \underbrace{3}_{\text{divisore}} \cdot \underbrace{1}_{\text{quoziente}} + \underbrace{2}_{\text{resto}}\]

Dunque, per sommare \(2\) a \(3\) in \(\mathbb{Z}_3\) si procede come segue:

  1. Prima si esegue la tipica operazione della somma. Sommando \(2\) a \(3\) otteniamo \(5\). In formula

    \[2 + 3 = 5\]

  2. Successivamente, per “ricondurre” il risultato dell’operazione precedente ad un elemento dell’insieme \(\mathbb{Z}_3\), l’idea è quella di dividere il numero ottenuto per \(3\) e prendere il resto di tale divisione. Nel nostro caso, dato che il resto di \(5\) diviso \(3\) è \(2\), scriviamo

    \[2 + 3 = 5 \mod 3\]

    Quel “mod 3” alla fine dell’equazione serve a ricordarci che stiamo lavorando in \(\mathbb{Z}_3\), ovvero modulo \(3\), e quindi dobbiamo sempre ricordarci di prendere il resto nella divisione per \(3\).

Dato che il resto nella divisione per \(3\) può essere \(0\), \(1\) o \(2\), prendendo il resto siamo assicurati che il numero risultante farà parte di \(\mathbb{Z}_3\).

Per quanto riguarda il prodotto \((*)\), l’idea è esattamente la stessa. Consideriamo adesso di voler calcolare

\[2 * 8 \mod 3\]

come al solito, prima effettuiamo la solita operazione, e poi riduciamo tutto tramite il resto della divisione per \(3\):

  1. Moltiplicando \(2\) ad \(8\) otteniamo \(16\). In formula,

    \[2 * 8 = 16\]

  2. Dividendo \(16\) per \(3\) otteniamo

    \[\underbrace{16}_{\text{dividendo}} = \underbrace{3}_{\text{divisore}} \cdot \underbrace{5}_{\text{quoziente}} + \underbrace{1}_{\text{resto}}\]

    quindi abbiamo resto \(1\) e possiamo scrivere

    \[2 * 8 \mod 3 = 1\]

Esercizi: Provate a risolvere questi esercizi da soli o con qualche calcolatrice:

  • \(1 + 15 \mod 3 = \;\;\;\; \text{?}\)

  • \(3 + 20 \mod 3 = \;\;\;\; \text{?}\)

  • \(3 * 20 \mod 3 = \;\;\;\; \text{?}\)

  • \(2 * 11 \mod 3 = \;\;\;\; \text{?}\)

L’importante non è necessariamente fare i calcoli manualmente. L’importante è capire ciò che si sta calcolando, e capire se la risposta che si ottiene ha senso rispetto al problema di partenza.

Osservazione n.3: Come possiamo vedere quindi, lo stesso simbolo, il simbolo della somma \((+)\), assume significati diversi a seconda del contesto matematico in cui ci troviamo.

Se lavoriamo nell’aritmetica tradizionale, la somma si comporta esattamente come ci hanno insegnato alle elementari, e possiamo scrivere

\[2 + 3 = 5\]

Se però lavoriamo nel contesto di \(\mathbb{Z}_3\), che è una particolare aritmetica modulare, quella ottenuta quando poniamo il modulo \(n = 3\), allora l’operazione è diversa, e si scrive

\[2 + 3 = 2 \mod 3\]

perché se dividiamo \(5\) per \(3\) otteniamo resto \(2\).

Un altro modo per scrivere la relazione di prima è il seguente

\[2 + 3 \equiv_3 2\]

Dove qui il simbolo \(\equiv\) viene utilizzato per indicare una relazione di equivalenza, che è un altro concetto matematico studiato nel contesto della matematica discreta che non tratterò in questo blog-post.

Sto scrivendo queste notazioni non per confondere, ma per far capire proprio ciò che menzionavo prima: che la matematica è un insieme di linguaggi, ciascuno dei quali ha una propria notazione.

L’importante, a mio avviso, è ricordarsi che i simboli devono semplificarci la vita. Non dobbiamo essere spaventati da simboli che non conosciamo; bisogna solo imparare, poco a poco, a conoscere il significato delle varie notazioni, capire perché sono state introdotte, e, se siamo abbastanza curiosi, inventarci dei nostri nuovi linguaggi matematici.

Tutto al fine di migliorare il modo in cui pensiamo, e, di conseguenza, la nostra vita e la vita delle persone attorno a noi.

L’aritmetica dell’orologio⌗

L’aritmetica modulare è molto spesso chiamata anche “aritmetica dell’orologio”. Questo strano nome deriva dal fatto che possiamo visulizzare i risultati delle operazioni in aritmetica modulare pensando alle lancette di un orologio.

Consideriano il caso particolare \(n = 12\), e dividiamo il solito quadrante dell’orologio in 12 linee, dove la prima la indichiamo con \(12\) e l’ultima con \(11\).

Rispetto a quanto trattato prima, basta fare sostituire lo \(0\) di prima con il \(12\) nella figura, e otteniamo esattamente l’insieme \(\mathbb{Z}_{12}\).

\[\mathbb{Z}_12 = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\]

Addizionare due numeri significa partire da una linea e saltare di un posto tanto quanto è il valore dell’altra linea. Come possiamo vedere, dopo l’\(11\) non c’è il \(12\), ma lo \(0\). In altre parole, lavorando modulo \(12\) abbiamo che

\[11 + 1 = 12 = 0 \mod 12\]

La figura dell’orologio tra l’altro ci fa vedere perfettamente cosa si intende quando si parla di “finitezza” dell’aritmetica modulare.

Come possiamo vedere, le linee di un orologio sono finite. Eppure, possiamo andare intorno all’orologio quante volte vogliamo, senza incappare in problemi di memoria, perché ogni volta il “contatore”, raggiunto il limite, torna all’inizio e resetta a \(0\).

Esponenziazione in un contesto modulare⌗

Quando lavoriamo nella tradizionale aritmetica l’esponenziazione non è altro che una moltiplicazione in successione.

In particolare quando scriviamo \(2^3\), con quel \(3\) sopra il \(2\), stiamo indicando la potenza – in questo caso \(3\) – a cui stiamo “elevando” la base – in questo caso \(2\). In altre parole,

\[2^3 = 2 * 2 * 2 = 8\]

Alri esempi, giusto per far capire l’idea

\[\begin{split} 5^2 &= 5 * 5 &= 25 \\ 4^3 &= 4 * 4 * 4 &= 64 \\ \end{split}\]

In generale quindi se scriviamo \(a^b\) stiamo indicando il numero che si ottiene moltiplicando \(a\) per se stessa \(b\) volte.

\[a^b = \underbrace{a * a * \ldots * a }_{b \text{ volte}}\]

Ora, la stessa idea di esponenziazione la possiamo trovare anche nel contesto modulare, ovvero nell’aritmetica modulare.

Fissiamo un modulo, diciamo \(n = 5\), e lavoriamo con gli elementi di \(\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}\).

Come è stato già trattato, per moltiplicare due elementi di \(\mathbb{Z}_5\) devo prima effettuare la tradizionale moltiplicazione, e poi divido il risultato per \(5\).

Ad esempio,

\[2 * 4 = 3 \mod 5\]

in quanto \(2 * 4 = 8\), e \(8\) diviso \(5\) da resto \(3\).

Questo significa che se invece devo calcolare \(2^4 \mod 5\), un possibile approccio potrebbe essere:

  • Mi calcolo \(2 * 2\) e prendo il resto nella divisione per \(5\), calcolandomi così facendo \(2^2 \mod 5\). In questo step otteniamo

    \[2 * 2 = 4 \mod 5\]

  • Poi prendo il risultato di prima, ovvero \(4\), lo moltiplico per \(2\), e di nuovo prendo il resto nella divisione per \(5\), ottenendo

    \[4 * 2 = 3 \mod 5\]

  • Continuando, applico lo stesso step di prima ma con il nuovo risultato, ovvero \(3\), per otenere

    \[3 * 2 = 1 \mod 5\]

Così facendo ho spezzato il calcolo di \(2^4\) in una serie di calcoli intermedi. Possiamo codificare la stessa idea nella seguente formula

\[2^4 \mod 5 = \underbrace{\underbrace{(\underbrace{(2 * 2 \mod 5)}_{4} * 2 \mod 5)}_{3} * 2 \mod 5}_{1} = 1\]

Cerchiamo ora di generalizzare quanto visto in precedenza.

Con “generalizzare” in matematica si intende l’atto di prendere qualcosa di molto pratico, come l’esempio appena mostrato, che utilizza specifici numeri fissati, per renderlo utilizzabile anche in altri contesti.

Sono tante e varie le tecniche che i matematici hanno sviluppato nel corso degli anni per cercare di astrarre e rendere il più generale possibili i risultati ottenuti. Nel nostro caso l’idea sarà quella di introdurre delle variabili per andare ad astrarre le quantità in gioco.

Questa parte potrebbe essere la più difficile da comprendere, ma questo è normale: comprendere la matematica significa, a tutti gli effetti, imparare una nuova lingua.

Consideriamo quindi il seguente problema computazionale.

PROBLEMA (esponenziazione modulare): Fissato un modulo \(n \in \mathbb{N}^+\) e presi due elementi \(a, b \in \mathbb{Z}_n\) vogliamo trovare un algoritmo che calcola il seguente valore

\[a^b \mod n\]

L’idea sarà quella di approcciare il problema utilizzando proprio il modo in cui definiamo il concetto di “elevare a potenza”, in quanto elevare a potenza significa esattamente moltiplicare in sequenza.

Possiamo descrivere lo pseudocodice dell’algoritmo nel seguente modo

Fissato un modulo n e due interi a, b:
   risultato = 1
   per i che varia da 0 a b - 1:
       risultato = (risultato * a) % n
   ritorna risultato

Notiamo bene che con il simbolo % stiamo proprio ad indicare l’operazione di dividere e prendere il resto. Se scriviamo quindi \(5 \;\; \% \;\; 3\) allora otteniamo \(2\), in quanto il resto di \(5\) diviso per \(3\) è proprio \(2\).

L’algoritmo non fa altro che definire una variabile il cui ruolo è quello di “accumulare” il risultato. Ad ogni iterazione del for loop, il risultato viene aggiornato, moltiplicando il risultato parziale precedente con il valore di \(a\) dato in input e riducendo il tutto modulo \(n\)

Dopo \(b\) iterazioni del loop, abbiamo esattamente \(a^b \mod n\), il valore ricercato, che ritorniamo come output.

La variabile risultato poi deve essere inizializzata ad 1 perché così facendo alla prima iterazione la variabile assume il valore a. Se ad esempio fosse 0 allora sarebbe sempre 0 (riesci a vedere il perché di questo?)

Segue una implementazione in python dello pseudocodice

def slow_exponentiation(a, b, n):
    assert b > 0 and n > 0, "both n and b must > 0 in mod exp!"

    result = 1
    for i in range(0, b):
        result = (result * a) % n
    return result

Il codice assert serve a garantire che l’input sia valido. In particolare sia \(n\) che \(b\) devono essere più grandi di \(0\), altrimenti l’algoritmo non può essere eseguito.

Per quanto riguarda il resto, non c’è molto da descrivere, in quanto è la traduzione esatta dello pseudo-codice.

L’algoritmo descritto quindi funziona. Il problema, l’unico vero problema, è il costo. Quanto cosa quell’algoritmo? E ancora prima: cosa si intende per “costo di un algoritmo”?

L’idea è che i nostri algoritmi dovranno, ad un certo punto, essere eseguiti da una macchina, e le macchina, per eseguire gli algoritmi, impiegano varie risorse, quali l’elettricità, ad esempio, ma anche il tempo stesso delle persone, se si tratta di programmi interattivi.

Dato che queste sono risorse estremamente finite ed estremamente preziose, dobbiamo stare attenti agli algoritmi che eseguiamo, e, in particolare, dobbiamo stare attenti al numero di istruzioni che questi algoritmi eseguono: più istruzioni significa più tempo di processamento, il che, a sua volta, significa più risorse consumate.

Per descrivere i costi di un algoritmo si utilizza una particolare notazione. Questa notazione si trova a cavallo tra la matematica e l’informatica, ed è nota con il nome di notazione asintotica.

Non è mia intenzione descrivere in dettaglio come leggerla e come scriverla, in quanto lascerò questo particolare argomento al blog-post della serie legato alla teoria degli algoritmi e delle strutture dati.

L’unica cosa che voglio menzionare è che, l’algoritmo appena descritto ha la seguente complessità computazionale:

\[T(n) = O(b \cdot (\log_2 n)^2)\]

dove \(\log_2 n\) è il logaritmo in base \(2\) di \(n\), ed è, essenzialmente, il numero di bit necessari per memorizzare \(a\).

Capisco che possa essere difficile interpretare correttamente tale formula, ma l’idea è che quella formula indica il fatto che l’algoritmo ha una complessità esponenziale, ovvero che il numero di istruzioni richieste dall’algoritmo cresce esponenzialmente rispetto alla grandezza dell’input.

Avere una complessità computazionale esponenziale è molto limitativo. Significa, in parole povere, che non possiamo utilizzare l’algoritmo in modo efficiente quando i numeri in input diventano troppo grandi.

Questo è un problema. Un problema di sicurezza.

Ebbene si, proprio di sicurezza, perché, tra i tanti crittosistemi introdotti nel corso della storia, uno tra questi è il crittosistema RSA, che per cifrare un messaggio utilizza proprio l’esponenziazione modulare.

Riuscire ad effettuare questa operazione in modo efficiente risulta quindi un qualcosa di necessario al fine di proteggere le nostre comunicazioni.

A questo punto ci si può quindi chiedere:

  • Si può fare di meglio?

  • Esistono degli algoritmi che risolvono lo stesso problema, ma con meno istruzioni?

La risposta, in questo caso, è positiva: si, esiste un algoritmo migliore, che non è né troppo complesso ma nemmeno troppo semplice.

È un algoritmo molto utile dal punto di vista didattico, perché mostra esattamente qual è il ruolo della teoria degli algoritmi, e perché abbiamo bisogno di questo tipo di conoscenza.

L’algoritmo verrà trattato nel blog-post relativo alla teoria degli algoritmi e delle strutture dati, in cui continuierò anche la discussione sulla notazione posizionale.