Crittografia

Aritmetica modulare

Consideriamo un orologio con le lancette e le ore indicate dai numeri da 1 a 12.

Spesso ci capita di sommare le ore. Ad esempio, se prendiamo il treno alle undici e viaggiamo per tre ore ci viene spontaneo dire che arriviamo in stazione alle due. In pratica abbiamo sommato i due numeri undici e tre e alla loro somma abbiamo tolto 12:

11 + 3 = 14; 14 - 12 = 2

E se partiamo alle 9 con una nave da crociera e questa arriva nel primo porto dopo 30 ore a che ora arriviamo? Alle tre.

9 + 30 = 39; 39 - 12 = 27; 27 - 12 = 15; 15 - 12 = 3

Possiamo anche procedere in un altro modo: sommare i due numeri e dividere il risultato per 12 e considerare il resto.

9 + 30 = 39; 39 : 12 = 3 con resto 3

In pratica quanto si sommano le ore si applica un calcolo modulare cioè, un'aritmetica modulo 12. Per esprimere questo tipo di aritmetica modulare si utilizza la notazione introdotta da Gauss:

9 + 30 mod 12 = 3

che si legge nove più trenta modulo 12 è uguale a tre. Questa scrittura ha vari significati, ad esempio:

se dividiamo 39 per 12 abbiamo come resto 3 oppure 39 - 3 è un multiplo di 12 oppure sia 39 che 3 divisi per 12 hanno lo stesso resto che è 3.

Se riflettiamo ci rendiamo conto che queste strane somme dipendono dal fatto che l'insieme dei numeri dell'orologio è finito ed è composto solo dai numeri da 1 a 12 e quindi la somma tra due o più ore non può essere maggiore di 12. Possiamo anche dire che l'aritmetica modulo 12 è un'aritmetica ciclica in quanto una volta raggiunto il numero 12 si ricomincia dal numero 1. In modo del tutto analogo potremo considerare la somma dei numeri in un qualsiasi insieme finito di numeri interi. Ad esempio, in un insieme finito costituito solo dai cinque numeri 0, 1, 2, 3, 4 potremo eseguire le addizioni modulo 5:

3 + 4 mod 5 = 2; 2 + 3 mod 5 = 0; 1 + 2 mod 5 = 3

E' come sommare le ore su un orologio con solo cinque ore.

Con lo stesso procedimento possiamo eseguire la moltiplicazione o l'elevamento a potenza nell'aritmetica modulare. Ad esempio:

3 ⋅ 4 mod 5 = 2; 2³ mod 5 = 3

Nell'aritmetica modulare valgono le stesse proprietà dell'aritmetica ordinaria rispetto all'addizione e alla moltiplicazione. Ad esempio:

11 mod 7 = 4; 8 mod 7 = 1; (11 mod 7) ⋅ (8 mod 7) = 88 mod 7 = 4

8 mod 11 = 8; 6 mod 11 = 6; (8 mod 11) + (6 mod 11) = 14 mod 11 = 3

Pierre de Fermat scoprí un'importante proprietà dell'aritmetica modulare denominata in seguito piccolo teorema di Fermat;

se il modulo è un numero primo p allora per ogni numero 1 ≤ a ≤ (p-1) se moltiplichiamo a per se stesso p-volte, si ottiene sempre il numero a.

a^p mod p = a

Ad esempio:

2³ mod 3 = 2; 2⁵ mod 5 = 2; 2⁷ mod 7 = 2;

E se dividiamo entrambi i membri per a diverso da 0, il piccolo teorema di fermat può essere scritto nella forma equivalente

a^p-1 mod p = 1

Eulero introdusse una nuova relazione detta funzione di Eulero indicata con la notazione φ(n):

Per ogni intero n positivo φ(n) è il numero di interi compresi tra 1 e n che sono coprimi con n.

(due numeri a e n sono coprimi se l'unico numero che li divide entrambi è 1 cioè MCD(a, n)=1)

Ad esempio per n = 10 si ha φ(n)=4 perchè i numeri coprimi con 10 sono 1, 3, 7, 9. E per ogni numero p primo la funzione di Eulero è uguale al numero (p-1) perchè p non ha fattori in comune, eccetto 1, con i numeri interi minori di p. Ad esempio:

φ(5) = 4 perchè i coprimi con 5 sono 1, 2, 3, 4

φ(7) = 6 perchè i coprimi con 7 sono 1, 2, 3, 4, 5, 6

Pertanto, il piccolo teorema di Fermat può essere scritto nella forma:

a^φ(n) mod p = 1

Eulero estese il piccolo teorema di Fermat al caso in cui il modulo n non sia primo. Se n è il prodotto di due numeri primi p e q e a è coprimo con n si ha:

a^(p-1)(q-1) mod n = 1

ed essendo φ(n) = (p-1)(q-1) possiamo scrivere

a^φ(n) mod n = 1

Ad esempio per n=15=3⋅5 si ha φ(3) = 2, φ(5) = 4, φ(15) = 8. Ora, se si sceglie un numero compreso tra 1 e 15 e coprimo con 15, ad esempio 2, possiamo verificare che:

2⁸ mod 15 = 1

Infatti:

2⁸ = 256 = 17 ⋅ 15 + 1