Qui Crescono Solo Polinomi

Chi mi conosce sa che uno dei temi che più mi appassionano è la crittografia. Per cui non era questione di se bensì di quando, avrei scritto un articolo a riguardo. Da che mondo e mondo però non si può partire a bomba, e questo articolo serve proprio a questo, a preparare il campo. No, non quello di Galois, quello verrà dopo. Quindi in questo post getteremo le basi di aritmetica modulare e dei campi di Galois, i quali sono le colonne portanti di tutta la crittografia moderna. Piccolo spoiler: ci saranno un po’ di numeri. Nulla di ingestibile, ma se la matematica non vi piace, arrangiatevi.

Mi Girano I Numeri

Come anticipato in questo primo paragrafo introduciamo un mattoncino fondamentale: l'aritmetica modulare. So che quando vedete i numeri è altro che vi gira, ma il titolo come vedremo è adatto all'argomento. L'aritmetica modulare è quella branca della matematica che studia le proprietà e le relazioni tra numeri interi, attraverso i concetti di congruenza e modulo. Cosa?! Chiedete quando due numeri \(a\) e \(b\) sono congruenti modulo \(n\) ? Ebbene quando \(b\) è il resto della divisione tra \(a\) ed \(n\). Questa relazione si scrive così:

Formula 1. Forma Base Congruenza

Sì, messa così sembra chissà quale cosa astratta ma in realtà è molto semplice e con qualche esempio è subito chiaro. Supponiamo di avere \(a=5\) e \(n=3\). La divisione \(\frac{5}{3}\) ha risultato \(1\) con resto di \(2\), per cui è vera la congruenza

Quindi, in aritmetica modulare, scrivere

o scrivere

è del tutto equivalente. Con questa logica è vera anche questa di congruenza:

dato che \(\frac{6}{3}\) ha risultato \(2\) con resto di \(0\).

Ora, so che non è il massimo del divertimento ma potete sbizzarrirvi a scrivere tutte le congruenze che volete. Di fatto sono solo relazioni tra numeri. E non fare l'errore di pensare che sono inutili, in realtà le utilizzate più spesso di quanto possiate immaginare.

Un esempio semplice è la lettura dell'ora. Ogni volta che guardate un orologio, state inconsapevolmente lavorando \(\pmod{24}\). Quando la giornata finisce, non continuate a contare le ore oltre il 24, ricominciate da capo. Così le 25 diventano l'1, le 27 diventano le 3, e via dicendo fino alla fine dei vostri giorni. Ogni "giro" dell’orologio è un'operazione modulare.

Essendo \(b\) un resto, va da sé che non potrà mai essere negativo, ma sarà sempre compreso tra \(0\) e \(n-1\). Se vi esce un resto sotto lo zero avete sbagliato qualcosa: troppo bello andare a fare la spesa, avere un “resto negativo” e vedere il cassiere che vi dà dei soldi. Purtroppo non funziona così, né nei supermercati, né nell'aritmetica modulare. Questa caratteristica porta a una proprietà fondamentale: l’aritmetica modulare è ciclica. Superato il modulo, i numeri si avvolgono su se stessi ricominciando il conteggio da 0. E anche se vi sembra una proprietà fine a se stessa, tutta la moderna crittografia si basa proprio su questo.

Una Regola Per Domarli

Risolvere una congruenza è molto semplice. Supponete di avere la seguente relazione:

Quello che l'equazione vi sta chiedendo è di trovare il resto della divisione di \(a\) per \(n\). Per risolverla si seguono tre passaggi molto semplici:

1. Si calcola:

   $$ z = \left\lfloor \frac{a}{n} \right\rfloor $$

2. Si calcola:

   $$ y = n \cdot z $$

3. Si calcola:

   $$ x = a - y $$

Questi tre semplici passaggi gestiscono sia le congruenze con valori positivi che quelle con valori negativi:

1. Caso 1:

   $$ x \equiv 13 \pmod{5} \\ z = \left\lfloor \frac{13}{5} \right\rfloor = \left\lfloor 2.6 \right\rfloor = 2 \\ y = 5 \cdot 2 = 10 \\ x = 13 - 10 = 3 $$

   ed infatti

   $$ 13 \equiv 3 \pmod{5} $$

2. Caso 2:

   $$ x \equiv -3 \pmod{5} \\ z = \left\lfloor \frac{-3}{5} \right\rfloor = \left\lfloor -0.6 \right\rfloor = -1 \\ y = 5 \cdot -1 = -5 \\ x = -3 - (-5) = 2 $$

   da cui

   $$ -3 \equiv 2 \pmod{5} $$

Il caso positivo è molto intuitivo, contrariamente a quello negativo che sembra campato in aria, no? No! Ha senso anche quello. Se state guardando l'orologio ed è precisamente mezzanotte, modularmente parlando sono le:

E se vi chiedessi: "un'ora fa che ore erano?" matematicamente sarebbe:

Ma voi, dall'alto della vostra straordinaria capacità di concepire il tempo, rispondereste:

(del giorno prima).

Si, Anche Le Frazioni

Abbiamo visto numeri positivi e numeri negativi, ma non finisce qui. Solo perché i resti sono sempre degli interi, non vuol dire che l'aritmetica modulare non sia in grado di gestire le divisioni. Se vi facevano strano i negativi, anche le frazioni modulari non sono da meno. La faccenda qui si fa un pochino più elaborata infatti, data l'equazione

affinché il risultato esista deve essere vera la condizione:

dove il \(GCD\) altro non è che il massimo comune divisore. Quando è vera i numeri si dicono tra di loro coprimi e possiamo risolvere le divisioni. La cosa non finisce certo qui, perché per poter risolvere è necessario applicare l'algoritmo di Euclide esteso e trovare i coefficienti dell'identità di Bézout. Senza entrare troppo nel dettaglio vediamo un esempio, solo per mostrarvi che non dico castronerie. Supponiamo di dover risolvere:

Che siano coprimi non c'è bisogno di dimostrarlo per cui partiamo subito applicando l'algoritmo di Euclide esteso che ci permette di scrivere:

e in questa uguaglianza, la \(x\) è proprio la soluzione che cerchiamo.

Facendo le dovute sostituzioni abbiamo:

Questa possiamo risolverla anche a mente, infatti ponendo \(x=-2\) e \(y=1\), rendiamo vera l'uguaglianza. Quindi la soluzione è \(x=-2\), ma ormai sappiamo che in aritmetica modulare i numeri negativi ci fanno schifo, per cui riportandoci a valori positivi abbiamo:

Quindi nella nostra equazione iniziale abbiamo:

Quello che abbiamo fatto in pratica, è stato trovare un inverso moltiplicativo, cioè abbiamo trovato un numero (il \(5\)) tale per cui, moltiplicato per un secondo (il \(3\)), e ridotto a modulo (di \(7\)) dia come resto \(1\). Questo è facile nella matematica di tutti i giorni, ad esempio l'inverso moltiplicativo di \(3\) è \(\frac{1}{3}\). Ma l'aritmetica modulare vive in un mondo tutto suo e l'inverso di \(3\pmod{7}\) è \(5\).

Conoscendo l'inverso moltiplicativo, si possono risolvere anche le equazioni. Supponiamo di avere:

Se andaste a calcolare l'inverso moltiplicativo di \(2\pmod{17}\) vedreste che è \(9\), per cui possiamo scrivere:

Questi sono esempi semplici, ma molto esplicativi di come funziona il calcolo dell'inverso in aritmetica modulare. Si possono fare ovviamente esempi più complessi ma esulano i miei scopi di dare una infarinata di questi concetti.

Ora che abbiamo preso confidenza facciamo un passo indietro. Prima ho scritto che è necessario che i numeri siano coprimi. Ecco ho mentito, almeno in parte. Anche se un po' tricky, ci sono dei modi per risolvere i casi in cui per una congruenza risulta

Senza entrare troppo nel merito vi basti sapere questo:

• Se \(GCD(a, n) = d > 1\) la congruenza è risolvibile se e solo se \(d \mid b\) (cioè \(d\) divide \(b\) dando un risultato intero).
• Se \(d \mid b\) abbiamo più di una soluzione per la congruenza (esattamente \(d\)).

Per farvi degli esempi:

• Esempio caso possibile

  $$ 4x \equiv 8 \pmod{12} $$

  Abbiamo che \(GCD(4, 12) = 4\) e dato che \(4\) divide \(8\) abbiamo 4 soluzioni che sono

  $$ x=2, 5, 8, 11 $$

  Anche se ho omesso il procedimento perché out of scope, provare per credere.

• Esempio caso impossibile:

  $$ 4x \equiv 1 \pmod{12} $$

  Abbiamo che \(GCD(4, 12) = 4\) e dato che \(4\) non divide \(1\) non abbiamo soluzioni.

Ovviamente non è tutto qui, si possono anche risolvere le equazioni di secondo grado, i sistemi di equazioni, ecc. Ma sono tutti argomenti che esulano lo scopo di una infarinatura generale, se volete approfondire vi consiglio di dare uno sguardo al libro riportato nei riferimenti.

Non Tutti I Campi Vengono Per Nuocere

L'aritmetica modulare è uno strumento molto potente. Abbinandola all'utilizzo dei numeri primi, avete come risultato la base per tantissimi algoritmi crittografici: RSA, Diffie-Hellman, El Gamal e via dicendo. Ci ha permesso di giocare con numeri, resti, ciclicità e ci siamo divertiti, ma quando il gioco si fa duro i duri cominciano a giocare e alcuni algoritmi di crittografia, senza fare nomi (le curve ellittiche), rompono gli zebedei. Dicono: "Tutti questi resti non ci bastano più!". Le curve ellittiche sono ingorde, vogliono più elementi. Ed è qui che entrano in gioco i famigerati campi. Non dei campi qualsiasi, bensí i campi finiti, ma andiamo per gradi.

Cosa è un campo... Un campo altro non è che un insieme di elementi i quali permettono di effettuare le operazioni di somma e moltiplicazione che rispettano alcuni requisiti:

1. Chiusura: sommando e/o moltiplicando gli elementi del campo, otteniamo un elemento nel campo. Supponiamo di avere un campo \(\mathbb{A}\) e due elementi \(a, \, b \neq 0 \, \in \mathbb{A}\), allora avere un campo chiuso vuol dire che \(a + b \in \mathbb{A}\) e \(a \cdot b \in \mathbb{A}\).
2. Gruppo Abeliano: le operazioni di somma e moltiplicazione, devono avere l'elemento neutro, il suo inverso e devono rispettare le proprietà associativa, commutativa e distributiva. Questo in parole povere vuol dire che, dato il campo \(\mathbb{A}\), \(a, \, b, \, c \in \mathbb{A}\) e \(a, \, b, \, c \neq 0\):
   • Esiste il termine \(0\) che permette di scrivere \(a + 0 = a\) (elemento neutro dell'addizione).
   • Esiste il termine \(1\) che permette di scrivere \(a \cdot 1 = a\) (elemento neutro della moltiplicazione).
   • Esiste il termine \(-a\) che permette di scrivere \(a - a = 0\) (inverso dell'addizione).
   • Esiste il termine \(a^{-1}\) che permette di scrivere \(a \cdot a^{-1} = 1\) ad esclusione dello \(0\) (inverso della moltiplicazione).
   • \(a + b = b + a\) e \((a + b) + c = a + (b + c)\) (proprietà commutativa e associativa dell'addizione).
   • \(a \cdot b = b \cdot a\) e \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) (proprietà commutativa e associativa della moltiplicazione).
   • \(a \cdot (b + c) = a \cdot b + a \cdot c\) (proprietà distributiva)

Sembra un listone di roba invece se leggete attentamente è tutto abbastanza semplice. Non ci sono proprietà strane, anzi sono tutte cose che si imparano alle elementari. Un esempio di campo è qualcosa che di fatto usate ogni giorno, l'insieme dei numeri reali \(\mathbb{R}\). Prendete due numeri reali qualsiasi e considerate uno per uno i punti elencati. Vedrete che tutti vengono soddisfatti. Lo stesso non si può dire ad esempio, per l'insieme dei numeri naturali \(\mathbb{N}\). I numeri naturali (a seconda della convenzione, con o senza lo zero) sono tutti gli interi positivi \({0, \, 1, \, 2, \, \dots}\), quindi non può essere comprensivo di un numero negativo e di conseguenza manca l'elemento inverso dell'addizione (per fare un esempio, dato che anche altre proprietà non vengono rispettate).

Praterie E Orticelli

Se siete arrivati fin qui, complimenti, ora sapete cosa è un campo. Detto questo, quand'è che un campo si definisce finito? Nulla di più intuitivo. Quando ha un insieme finito di elementi. Quando potete contare gli elementi del campo sapendo che prima o poi il conteggio termina. Quindi non solo deve rispettare i punti definiti in precedenza, ma deve anche avere un numero finito di elementi. Quindi \(\mathbb{R}\) è sí un campo, ma non è un campo finito perché contiene un numero infinito di elementi. Se è concettualmente semplice sapere cosa è un campo finito, costruirlo non è così immediato. O almeno non lo è per far contente le curve ellittiche (sí sono cosciente del fatto che sono due volte che le nomino ma non dico cosa sono, vi basti sapere che sono curve algebriche usate in ambito crittografia, magari un giorno ne parlerò). Quindi andiamo per passi. Sappiamo cosa è un campo finito, ebbene campo finito è un nome diverso per indicare un campo di Galois. Sono esattamente la stessa cosa.

Prima di procedere con il resto però, ci tengo a fare una piccola marchetta al grande Évariste Galois, dal cui nome derivano appunto i campi di Galois. Fu un grande matematico morto alla tenera età di 20 anni. Io a quell'età mi ubriacavo alle serate universitarie, lui inventava una branca dell'algebra astratta. Ma almeno io i 20 anni li ho superati (solo perché i duelli a singolar tenzone non esistono più). Ma torniamo a noi...

In realtà, nel paragrafo precedente abbiamo iniziato a vedere i campi finiti, ma non basta, dobbiamo aggiungere qualcosa. Torniamo alla cara aritmetica modulare considerando la forma base, e supponiamo di prendere un numero primo come valore di \(n\) (che i numeri primi siano quei numeri divisibili solo per 1 e per se stessi non c'è bisogno di dirlo vero?!). Considerando \(n=5\) abbiamo:

Dal paragrafo precedente dovreste sapere che tutti i possibili resti sono nell'insieme

Andiamo a verificare una per una le condizioni:

1. Chiusura:

   Consideriamo l'operazione di addizione e prendiamo, ad esempio, i valori \(4\) e \(3\) (ma è valido per tutti, fidatevi)

   $$ 4 + 3 = 7 \equiv 2 \pmod{5} $$

   cioè scrivere \(7 \pmod{5}\) è equivalente a scrivere \(2 \pmod{5}\), quindi siamo tornati nell'insieme \(\mathbb I\). Con la moltiplicazione otteniamo la stessa cosa:

   $$ 4 \cdot 3 = 12 \equiv 2 \pmod{5} $$
   siamo ancora all'interno di \(\mathbb{I}\).

2. Elemento neutro dell'addizione:

   Consideriamo l'operazione di addizione e prendiamo, ad esempio, il valore \(4\) (ma anche qui è valido per tutti, fidatevi)

   $$ 4 + 0 = 4 \equiv 4 \pmod{5} $$

   Anche questo torna, ottimo.

3. Elemento neutro della moltiplicazione:

   Consideriamo l'operazione di moltiplicazione e prendiamo, ad esempio, il valore \(4\) (ma anche qui è valido per tutti, fidatevi)

   $$ 4 \cdot 1 = 4 \equiv 4 \pmod{5} $$

   Anche questo torna, yu-hu.

4. Inverso dell'addizione:

   Consideriamo l'operazione di addizione e prendiamo, ad esempio, il valore \(4\) (stessa storia). L'inverso additivo è \(-4\), ma ormai sapete come gestire i valori negativi no?! Per cui saltando i passaggi scriviamo:

   $$ -4 \equiv 1 \pmod{5} $$

   quindi l'inverso additivo di \(4\), è \(1\). Infatti:

   $$ 1 + 4 = 5 \equiv 0 \pmod{5} $$

   Anche questo torna, evvai.

5. Inverso della moltiplicazione: qui non faró i passaggi ma riflettiamo sull'insieme \(\mathbb I - \{ 0 \}\). Una volta eliminato lo \(0\) che per definizione non ha inverso, ogni elemento di \(\mathbb I\) è coprimo con \(5\) essendo quest'ultimo un numero primo. E prima ho chiaramente scritto che se i numeri sono coprimi, esiste l'inverso. Quindi abbiamo la certezza che per ogni elemento di \(\mathbb I - \{ 0 \}\) abbiamo un inverso e di conseguenza anche questo punto ce lo portiamo a casa.

6. Beh ragá, io mi sarei pure un pó stufato. Gli ultimi tre sono varianti di addizioni e moltiplicazioni, se avete sbatti di prendere carta e penna e fatele, altrimenti fidatevi che anche quelli tornano.

Abbiamo quindi mostrato che se \(n\) è un numero primo, l'insieme dei resti forma un campo di Galois e la sua notazione formale è \(GF(p)\) o \(\mathbb{F}_p\) dove \(p\) è il numero primo scelto.

Vediamo perché, se \(p\) fosse non primo, non potremmo avere un campo di Galois. Consideriamo il caso \(p=8\), abbiamo che l'insieme dei resti è:

Prendiamo uno dei resti, \(b=2\), e cerchiamone l'inverso moltiplicativo. Per farlo dobbiamo scrivere la congruenza:

Da cui:

Andando a controllare la divisibilità si ha che \(2 \nmid 1\), e possiamo concludere che \(2 \pmod{8}\) non ha inverso moltiplicativo, e questo viola una delle proprietà richieste dai campi.

Dall'Orticello Alla Piantagione

Abbiamo visto che \(p\) deve essere primo per poter definire un campo di Galois. Ma se vi dicessi che invece si possono definire campi del tipo \(\mathbb{F}_8\)? No non sono impazzito. Si può fare, ma in maniera leggermente diversa rispetto a prima. Innanzi tutto iniziamo dicendo che l'argomento del campo, non può essere un numero qualsiasi, ma deve essere potenza di un numero primo. Quindi perché può esistere \(\mathbb{F}_8\)? Perché possiamo scrivere \(8=2^3\), cioè \(8\) come potenza del numero primo \(2\).

Anche se non è così, supponiamo che vi stiate chiedendo il perché sia utile farlo. Nel paragrafo precedente abbiamo visto che per ottenere un campo di Galois è necessario avere un numero primo \(p\), e il campo \(\mathbb{F}_p\) avrà esattamente \(p\) elementi:

Questo è un pó limitante non vi pare? Se volessimo un campo di Galois molto grande ma con primi piccoli? Ad esempio con \(2\)? Questo permetterebbe di avere tutti i termini numerici in \(\{0, \, 1\}\) ma con un numero di elementi più elevato di due. Questo ci permetterebbe non solo di ottenere un campo con molti più elementi, ma anche di lavorare con valori estremamente facili da gestire: rimanendo confinati a \(0\) e \(1\), le operazioni diventano naturalmente efficienti da rappresentare e da eseguire nei calcolatori, con notevoli vantaggi in termini di performance. No non è stregoneria. Si può fare ed è molto utile farlo, perché permette di avere numeri di valore basso, ma in campi molto grandi (il che aumenta la sicurezza delle famigerate curve ellittiche). Ok, ma come? Se i numeri sono quelli a cosa ricorriamo per aumentare la cardinalità del campo? La risposta è: ai polinomi. I polinomi agiscono come blocchi costruttivi: combinano i valori di \(\mathbb{F}_p\) in forme complesse, permettendoci di creare molti più elementi senza introdurre nuovi numeri, ma solo come nuove combinazioni degli stessi coefficienti. Per cui, dato un numero primo \(p\) e dato un esponente \(m\), possiamo definire grazie ai polinomi un campo \(\mathbb{F}_{p^m}\) di \(p^m\) elementi, i cui termini numerici sono in \(\{ 0, \, \dots, \, p - 1 \}\).

Considerando il caso \(\mathbb{F}_{2^3}\), andiamo a vedere per step (anzi, per gradi), come procedere:

• Grado \(m=0\): Questo caso è semplice, dobbiamo prendere i polinomi di grado \(0\) che di fatto sono i soli coefficienti. Dato che siamo in \(p=2\), i coefficienti sono

  $$ \{0, \, 1 \} $$

• Grado \(m=1\): In questo caso prendiamo tutti i polinomi di grado al più \(1\). La famiglia di questi è data da

  $$ q(x) = ax + b $$

  dato che i coefficienti devono essere in \(\{0, \, 1 \}\), abbiamo che questi polinomi sono:

  $$ \{x, \, x + 1 \} $$

  Infatti se:

  • \(a=0, \, b=0\) \(\Rightarrow q(x)=0\). Giá considerato in precedenza.
  • \(a=0, \, b=1\) \(\Rightarrow q(x)=1\). Giá considerato in precedenza.
  • \(a=1, \, b=0\) \(\Rightarrow q(x)=x\).
  • \(a=1, \, b=1\) \(\Rightarrow q(x)=x + 1\).

  Non ci possono essere polinomi di grado \(1\) come \(2x\) perché lavorando, in questo caso, con \(\pmod{2}\) abbiamo che

  $$ 2 \equiv 0 \pmod{2} \Rightarrow 2x \equiv 0 \pmod{2} $$

  che abbiamo giá considerato nel caso \(m=0\).

• Grado \(m=2\): Analogamente a prima, prendiamo tutti i polinomi di grado al più \(2\) i cui coefficienti sono in \(\{0, \, 1 \}\). La famiglia di questi è data da

  $$ q(x) = ax^2 + bx + c $$

  Quindi andando a sviluppare, e ignorando tutti quelli giá considerati in precedenza abbiamo:

  $$ \{x^2, \, x^2 + 1, \, x^2 + x, \, x^2 + x + 1 \} $$

• Grado \(m=3\): Eh, qui la situazione cambia. Iniziamo dicendo che lavorando in \(m=3\) non dobbiamo andare oltre. Questi polinomi non andranno a fare parte del campo, bensì andranno a definire il modulo del campo. Quando andiamo a cercare i polinomi di grado massimo rispetto al campo, dobbiamo assicurarci che siano irriducibili, cioè che non possano essere scritti come prodotto dei polinomi tra quelli finora elencati. I polinomi sono della famiglia

  $$ q(x) = ax^3 + bx^2 + cx + d $$

  In totale ci sono \(8\) polinomi, ma quelli irriducibili sono solo due:

  $$ \{x^3 + x + 1, \, x^3 + x^2 + 1 \} $$

  Provateci quanto vi pare, non riuscirete mai a scrivere questi due polinomi, come prodotto di due polinomi di grado inferiore. Vediamo rapidamente perché ignoriamo gli altri. Supponiamo di avere:

  $$ q(x) = x^3 + x^2 + x $$

  Questo possiamo scriverlo anche come:

  $$ q(x) = x^3 + x^2 + x = x \cdot (x^2 + x + 1) $$

  Essendo scrivibile come prodotto di due polinomi di grado inferiore, lo scartiamo perché vorrebbe dire introdurre elementi che non hanno inverso moltiplicativo.

Siamo quasi giunti alla fine. Ora che abbiamo i polinomi irriducibili ne scegliamo uno a piacere, quello che preferite (anche se io mi farei controllare se preferissi un polinomio rispetto un altro). In questo caso i campi si dicono isomorfi (stessa cardinalità, stessa struttura di campo ma polinomio irriducibile diverso). Supponiamo di scegliere il polinomio:

abbiamo trovato il nostro campo di Galois \(\mathbb{F}_{8}\) che contiene esattamente \(8\) elementi ridotti modulo il polinomio scelto, tutti i coefficienti calcolati \(\pmod{2}\) e che rispetta le proprietà sopra menzionate (altrimenti non sarebbe un campo di Galois):

Prendiamo due valori a caso e vediamo come, fare somma e prodotto degli elementi nel campo, non ci fa mai uscire dal campo stesso. Prendiamo \(f(x) = x^2 + 1\) e \(g(x) = x + 1\).

• Somma:

  $$ f(x) + g(x) = x^2 + x + 2 $$

  Dato che siamo in \(\pmod{2}\) abbiamo che

  $$ 2 \equiv 0 \pmod{2} $$

  Per cui possiamo scrivere

  $$ x^2 + x + 2 \equiv x^2 + x \pmod{2} $$

  cioè è tornato ad essere un polinomio appartenente al campo definito in precedenza.

• Prodotto:

  $$ f(x) \cdot g(x) = (x^2 + 1) \cdot (x + 1) = x^3 + x^2 + x + 1 $$

  Dato che il nostro polinomio irriducibile è \(x^3 + x^2 + 1\) possiamo scrivere questa relazione:

  $$ x^3 + x^2 + 1 \equiv 0 \pmod{x^3 + x^2 + 1} $$

  Da cui

  $$ x^3 \equiv -x^2 - 1 \pmod{x^3 + x^2 + 1} $$

  Vi ricordo però, che all'aritmetica modulare, i numeri negativi non piacciono ma sappiamo giá come riportarci in resti positivi \(\pmod{2}\). Omettendo i passaggi (che giá dovreste conoscere ma che potete leggere qui), abbiamo che:

  $$ -1 \equiv 1 \pmod{2} $$

  Quindi possiamo scrivere questo:

  $$ -x^2 - 1 \equiv x^2 + 1 \pmod{2} $$

  da cui possiamo scrivere:

  $$ x^3 \equiv x^2 + 1 \pmod{x^3 + x^2 + 1} $$

  Tornando ora al polinomio iniziale possiamo scrivere:

  $$ x^3 + x^2 + x + 1 \equiv x^2 + 1 + x^2 + x + 1 \equiv 2x^2 + x + 2 \pmod{x^3 + x^2 + 1} $$

  Dato che, come giá detto e ridetto, mostrato e rimostrato, siamo in \(\pmod{2}\) abbiamo che:

  $$ 2x^2 \equiv 0 \pmod{2}, \, 2 \equiv 0 \pmod{2} $$

  Siamo quindi giunti alla conclusione che:

  $$ (x^2 + 1) \cdot (x + 1) \equiv x \pmod{x^3 + x^2 + 1} $$

  e guarda caso, \(x\) è un polinomio del campo di Galois.

Per ovvi motivi vi ho dimostrato solo la proprietà di chiusura, ma siete liberissimi di fare tutti i vostri esperimenti. Tanto ho ragione io.

Per concludere questo paragrafo, vi invito ad usare un polinomio riducibile come modulo del campo. Carta e penna alla mano, vedrete che ci sarà almeno un elemento del campo che non ha un inverso moltiplicativo appartenente al campo stesso, violando una delle proprietà.

Conclusioni

Quando ho iniziato a scrivere questo articolo me lo ero figurato più corto, molto più corto. Ma questa volta non mi sono lasciato prendere la mano, il problema è che, col senno di poi, le cose da dire erano molte di più. Mi perdonerete se non avete visto casi più complicati dell'algoritmo di Euclide esteso o se non vi ho mostrato il teorema cinese del resto per risolvere sistemi di congruenze. Certo ora se il sabato sera uscite con il vostro (o la vostra) crush, non potete dire di sapere come risolvere una congruenza di secondo grado, ma potete parlare di Galois e dei campi finiti. Volete mettere. In ogni caso anche se tutte queste cose sembrano fine a loro stesse, sappiate che sono la base di tutte le operazioni che fate ogni giorno e che auspicate sicure. Se vi sentite al sicuro quando effettuate operazioni online, se vi sentite protetti sotto l'ombrello di RSA, delle curve ellittiche e via dicendo, sappiate che è grazie a questi elementi base, e un giorno ve ne parlerò. Fino ad allora però, non mi venite a dire "mi hanno hackerato la password", perché la crittografia è sicura, sono le password 1234 e la mamma calda a 3km da voi a non esserlo. Quindi è colpa vostra.

Alla Prossima.

---

Riferimenti

• https://it.wikipedia.org/wiki/Algoritmo_esteso_di_Euclide
• https://it.wikipedia.org/wiki/Identit%C3%A0_di_B%C3%A9zout
• Introduction to Cryptography with Coding Theory