Renato Betti


 

L'ARITMETICA MODULARE

Nelle Disquisitiones Arithmeticae (1801), Gauss mette in evidenza l'importanza della relazione di "congruenza" fra numeri interi, già nota ed utilizzata da tempo; e della relativa "aritmetica modulare" nella quale le operazioni si calcolano "modulo" un prefissato numero naturale. Per la relazione di congruenza fissa una notazione; che utilizziamo tuttora, e che la fa assomigliare all'uguaglianza.

Definizione. Dati gli interi relativi a, b appartenenti a Z ed il numero naturale n appartenente a N; si dice che a e b sono congrui modulo n; e si scrive a≡b (mod n); se esiste k appartenente a Z tale che a-b=kn.

E' facile vedere che la relazione di congruenza modulo n induce una relazione di equivalenza in Z, tale che appartengono alla stessa classe tutti e soli gli interi che hanno lo stesso resto quando sono divisi per n. Di conseguenza esistono n classi di equivalenza, rappresentate rispettivamente dagli interi 0, 1, 2, ...n -1, il cui insieme, cioè l'insieme quoziente Z/≡, si denota solitamente con Zn:

Zn={0,1,2,...,n-1}

Zn viene detto insieme delle classi dei resti modulo n.
La proprietà fondamentale della relazione di congruenza modulo n è la sua stabilità rispetto alle operazioni di somma e di prodotto. In altri termini:

Ciò significa che la classe di congruenza di una somma (o di un prodotto) non dipende dai rappresentanti n che si sono scelti per gli addendi (o per i fattori). Questo fatto permette di definire in Zn le operazioni di somma e prodotto in modo che là proiezione canonica sul quoziente ZZn sia un omomorfismo di anelli.
In sostanza, rispetto alle operazioni di somma e di prodotto, la congruenza si comporta come se fosse l'uguaglianza e da questo dipende forse la scelta dei simboli da parte di Gauss. Ciò non è vero per l'altra operazione razionale, la divisione, per la quale la stabilità dipende dal modulo n. Precisamente si ha:

a*c≡b*c (mod n) ==> a≡b (mod n)
se e solo se MCD(c, n) = 1


Grazie a questa, proprietà è tacile verificare che, quando MCD(a,n)=1, l'operazione di prodotto per a fornise una permutazione in Zn (precisamente è un isomorfismo di anelli) e quindi si ricava:

Teorema. La congruenza di primo grado a*x≡b (mod n) ha un'unica soluzione a meno di congruenze modulo n (cioè in Zn) se e solo se MCD(a,n)=1.

In particolare, sotto la condizione MCD(a,n)=1, l'esistenza della soluzione non dipende da b e la classe rappresentata da a ammette inverso a-1 in Zn: l'unica soluzione della congruenza a*x≡b (mod n) si scrive nella forma consueta a-1b (in Zn). Da qui si ricava, anche che Zn ha la struttura algebrica di "campo" se e solo se n è un numero primo: infatti in questo caso, e solo in questo caso, ogni a ≠0 risulta primo con n e quindi la classe dì congruenza rappresentata da a è invertibile in Zn.

 


LA φ DI EULERO

Una funzione aritmetica molto particolare è stata messa in rilievo da Eulero (1707-1783) per le sue speciali proprietà. Questa funzione prende il nome di "indicatrice" oppure "funzione totiente" o semplicemente " φ Eulero".

Definizione. La funzione aritmetica φ: N -> N associa ad ogni m≠1 minori di m e primi con m. Inoltre, si pone φ(1)=1.
In sostanza, φ(n) indica il numero di elementi invertibili in Zn. Così:

φ(1)=1
φ(2)=1
φ(3)=2
φ(4)=2
φ(5)=4
φ(6)=2
...

in generale, per conoscere φ(n) è necessario conoscere la scomposizione in fattori primi dell'argomento n,
grazie ai seguenti fatti:
1. φ(p) = p - 1 se p è primo;
2. φè una "funzione moltiplicativa", vale a dire φ(m*n)=φ(m)*φ(n) quando i fattori m e n son primi fra di loro, cioè MCD(rn, n)=1;
3. se p è primo, allora, φ(ph)=(p-1)ph-1.
Così, se si ha la scomposizione in fattori primi

usando le proprietà precedenti si ricava:


Un risultato fondamentale relativo alla φ, e dimostrato da Eulero nel `700, è il seguente:

Teorema (di Eulero-Fermat). Se a ed n sono due interi assoluti primi fra di loro, cioè MCD(a, n)=1, allora:

aφ(n)≡1 (mod n)

Si osservi che in questo risultato compare il nome del famoso matematico (e magistrato di Tolosa) Pierre de Fermat (1601-1665), in quanto si tratta della generalizzazione di un altro risultato, trovato da Fermat nel corso del secolo precedente:

Teorema (piccolo teorema, di Fermat). Se p è un numero primo ed a non è divisibile per p, allora:


ap-1≡1 (mod n)

Si riconosce che questo è un caso particolare del precedente perché, quando p è primo, φ(p)=p-1 e inoltre la condizione MCD(a; p)=1 si esprime semplicemente dicendo che a non è divisibile per p.



BIBLIOGRAFIA

[1] A. Sgarro, Crittografia, Muzzio, 1985

[2] A. Beutelspacher, Cryptology, MAA 1994 (versione italiana estesa: L. Berardi, A. Beutelspacher, Crittologia. Come proteggere le informazioni riservate, Franco Angeli 1996)

[3] S. Singh, Codici e segreti, Rizzoli 1,999 (ed. originale: The Code Book, 1999)

[4] C. Giustozzi, A. Monti, E. Zimuel, Segreti, spie, codici cifrati. Crittografia: la storia, le tecniche, gli aspetti giuridici, Apogeo 1999

[5] C. Shannon, Communication Theory of Secrecy Systems, Bell Systems Technical Journal 1949

[6] A. Hodges, Storia di un enigma: vita di Alan Turing; Bollati Boringhieri 1991 (ed. originale: Enigma, 1983)

[7] W. Diffie, M.E. Hellman, New Directions in cryptoqraphy, IEEE Transactions on Information Theory, 1976

[8] R. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Communications ACM, 1978

[9] A. Salomaa, Public-Key Cryptography. Springer 1990

[10] P. Ferragine, F. Luccio, Crittografia. Principi, algoritmi, applicazioni, Bollati Boringhieri 2001

[11] N. Koeblitz, A Course in Number Theory and Cryptography, Springer 1987

[12] C. Pomerance (ed.), Cryptology and Computational Number Theory, AMS 1990