Sia mє Z.
Si ricordi che:
(1) Se a e b sono numeri interi, si dice che a è congruo a b modulo m se a-b è un multiplo di m; in questo caso, si scrive a≡b (mod m).
(2) La relazione binaria così definita è una congruenza nell’anello (Z, +, ∙), che viene chiamata congruenza modulo m.
(3) La classe di equivalenza di un numero intero a viene indicata con il simbolo [a]m e chiamata classe di congruenza di a modulo m; per ogni numero intero a, si ha [a]m ={ a+km | kє Z}; in particolare, [0]m coincide con l’insieme dei multipli di m.
(4) L’insieme quoziente { [a]m | a є Z} viene indicato con il simbolo Zm.
In Zm si introducono le operazioni quoziente + e ∙ ponendo per ogni coppia (a,b) di numeri interi
[a]m+[b]m=[a+b]m e [a]m ∙ [b]m=[a ∙ b]m
(5) Se m≠0, allora ogni numero intero a è congruo modulo m al resto della divisione euclidea di a per m.
(6) Se m>1, Zm={ [0]m , [1]m , … , [m-1]m }.
Se un numero intero m è multiplo di un numero intero n, allora ovviamente [a]m ⊆ [a]n . Si ha inoltre
Proposizione 3.1
Sia m un numero intero tale che m>1. Se m=nt con n,t>1, allora per ogni numero intero a,
[a]n = [a]m U [a+n]m U … U [a+(t-1)n]m
e
l’insieme { [a]m , [a+n]m , … , [a+(t-1)n]m ha } ha ordine t
Dimostrazione
Per ogni j=0,…, t-1, si ha [a+jn]m ⊆ [a+jn]n =[a]n ,
⇒ [a]m U [a+n]m U … U [a+(t-1)n]m ⊆ [a]n .
Viceversa sia b un elemento di [a]n e sia k un numero intero tale che b=a+kn. L’algoritmo della divisione euclidea applicato a k e t assicura che esistono q,r tali che k=tq+r con 0 ≤ r≤ t-1 ,
⇒ b=a+kn=a+mq+rn=(a+rn)+mq⇒ b è un elemento di [a+rn]m .
Dunque [a]n = [a]m U [a+n]m U … U [a+(t-1)n]m
Siano ora i e j numeri interi tali che 0≤ i≤ j≤ t-1 e [a+in]m = [a+jn]m ,
⇒ (j-i)n è un multiplo di m; d’altra parte 0≤ (j-i)n < tn=m
⇒ j-i=0.
Dunque l’insieme { [a]m , [a+n]m , … , [a+(t-1)n]m } ha ordine t.
I concetti presentati in questa slide fanno parte dei contenuti dei corsi di Algebra del primo anno, ma vengono esplicitamente richiamati, in quanto verranno più volte utilizzati nel seguito.
(1) Se G è un gruppo e gє G, allora <g> = { gn | n є Z}.
Se il gruppo G è dato con notazione additiva, allora <g> = { n g | n є Z}.
(2) Sia G un gruppo e sia gє G.
Si dice che g è periodico se <g> è finito, e, in questo caso, l’ordine di <g> si chiama periodo di g.
Si dice invece che g è aperiodico se <g> è infinito.
(3) Si ricordi che un gruppo C si dice ciclico se esiste un elemento x di C tale che C=<x>; in questo caso si dice che x è un generatore di C.
(4) I sottogruppi e i quozienti di un gruppo ciclico sono ciclici.
(5) Il gruppo (Z,+) è un gruppo ciclico infinito i cui unici generatori sono 1 e -1.
Se m è un numero intero, allora <m> coincide con l’insieme dei multipli di m.
Una parte non vuota H di Z è un sottogruppo di (Z,+) se e solo se esiste un intero m tale che H=<m>.
(6) Se m è un numero intero, il gruppo (Zm ,+) è un gruppo ciclico finito di ordine m.
[1]m e [-1]m=[m-1]m sono generatori di (Zm ,+).
Nella Lezione 5 verranno descritte alcune proprietà dei gruppi ciclici finiti.
(Z ,+ , ∙) è un anello commutativo unitario; gli unici elementi invertibili di (Z , ∙) sono 1 e -1.
Per ogni numero intero m, (Zm ,+ , ∙) è un anello commutativo unitario.
Lo studio della struttura dell’anello (Zm ,+ , ∙) costituisce la branca dell’aritmetica detta aritmetica modulare, che ha molte applicazioni, non solo in crittografia, ma anche in diverse branche della matematica e dell’informatica.
Si affronterà ora il problema di individuare gli elementi invertibili di (Zm , ∙)
Teorema 3.2
Sia m un numero intero tale che m >1, e sia a un numero intero. Allora:
(1) [a]m è un elemento invertibile di (Zm , ∙) se e solo se a e m sono coprimi.
(2) se a e m sono coprimi e u , v sono numeri interi tali che 1=au+mv, allora [u]m=[a]m-1 .
Dimostrazione
Si supponga in primo luogo che [a]m sia un elemento invertibile di (Zm , ∙)
⇒ esiste un numero intero a’ tale che [a]m ∙ [a']m = [1]m
⇒ aa’ ≡ 1 (mod m)
⇒ esiste un numero intero k tale che 1=aa’+km
⇒ 1 e -1 sono gli unici divisori comuni di a e m.
Viceversa, se a e m sono coprimi, allora esistono u,v є Z tali che au+mv=1
⇒ [a]m ∙ [u]m = [1]m
⇒ [a]m è un elemento invertibile di (Zm , ∙) .
Teorema 3.3
Sia m un numero intero tale che m>1.
(Zm , + , ∙) è un campo se e solo se m è un numero primo.
Dimostrazione
Si supponga in primo luogo che (Zm , + , ∙) sia un campo. Sia a un divisore di m tale che a sia diverso da m e da -m
⇒ a non è un multiplo di m
⇒ [a]m è un elemento di Zm diverso da [0]m
⇒ [a]m è un elemento invertibile di Zm
⇒ a e m sono coprimi
⇒ a=± 1.
Dunque m è primo.
Viceversa, si supponga che m sia primo.
Sia [a]m un elemento di Zm\{[0]m}
⇒ a non è un multiplo di m
⇒ a e m sono coprimi
⇒ [a]m è un elemento invertibile di (Zm , ∙).
Dunque (Zm , + , ∙) è un campo.
Sia m un numero intero tale che m>1.
Con il simbolo U(Zm ) si indica l’insieme
{ [a]m є Zm | [a]m è un elemento invertibile di (Zm , ∙) }.
Allora U(Zm) è una parte stabile di (Zm , ∙) e la struttura algebrica Zm* = (U(Zm) , ∙) è un gruppo.
Definizione 3.4
Si consideri la funzione φ definita ponendo:
φ (n)= |{ b є N tali che 1 ≤ b ≤ n e (b,n)=1}|
Tale funzione φ si chiama Funzione di Eulero.
Ovviamente, φ (1)=1 e se p è un numero primo positivo, φ(p)=p-1.
Più in generale, se p è un numero primo positivo e β è un numero naturale positivo, si ha
{b є N tali che 1 ≤ b ≤ pβ e (b,pβ)=1} =
= {b є N tali che 1 ≤ b ≤ pβ e p non divide b} =
= {b є N tali che 1 ≤ b ≤ pβ} \ {ph | 1 ≤ h ≤ pβ-1}
⇒ φ (pβ) = pβ – pβ-1 = pβ-1 (p-1)
Segue dal Teorema 3.3 che |Zm*|=φ(m).
In seguito verranno presentate altre proprietà della funzione di Eulero.
1. Espansione di un numero naturale in base b e complessità computazionale delle operazioni elementari
2. Complessità dell'algoritmo delle divisioni successive
3. Struttura dell'anello degli interi modulo m, funzione di Eulero
4. Equazioni congruenziali lineari e Teorema Cinese del Resto
5. Teorema di Fermat-Eulero e Piccolo teorema di Fermat. Alcune proprietà dei gruppi ciclici finiti
6. Cifrario di Cesare. Cifrario di Vigenere. Metodo di Hill
7. Richiami sui campi finiti. Generalità sulle curve ellittiche
10. RSA. Sistema di di Massey-Omura. Sistema di El Gamal
11. Immersione dei testi in chiaro e sistemi crittografici in una curva ellittica
12. Resti quadratici e simbolo di Legendre
13. Condizioni necessarie e condizioni sufficienti per la primalità; forme di pseudoprimalità
15. Test di Solovay-Strassen e Test di Miller-Rabin
16. Test di primalità basato sulle curve ellittiche e test AKS