Definizione 4.1
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
La funzione
f: Z → Zm definita ponendo f(c)=[ac-b]m
si chiama equazione congruenziale lineare di termini a e b e modulo m e si denota con il simbolo
ax ≡ b (mod m).
Definizione 4.2
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
Si dice che un numero intero c è soluzione dell’equazione congruenziale ax ≡ b (mod m) se ac ≡ b (mod m).
Proposizione 4.3
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
L’equazione ax ≡ b (mod m) ha soluzioni se e solo se b è multiplo dei massimi comun divisori di a e m.
Dimostrazione
Si supponga in primo luogo che l’equazione ax ≡ b (mod m) abbia una soluzione c
⇒ ac ≡ b (mod m)
⇒ esiste un numero intero k tale che b=ac+km
⇒ b è multiplo di ogni divisore comune di a e m.
Viceversa, si supponga che b sia multiplo dei massimi comun divisori di a e m; sia d un massimo comun divisore di a e m e siano b1 e u numeri tali che d=au+mv e b=db1
⇒ b=db1= (au+mv)b1 =aub1 + mvb1 ≡ aub1 (mod m)
⇒ ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).
Teorema 4.4
Sia m un numero intero tale che m>1, e siano a,b numeri interi tali che b è multiplo dei massimi comun divisori di a e m. Allora:
(1) Sia d un massimo comun divisore di a e m e siano b1 e u numeri tali che d=au+mv e b=db1 . Allora ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).
(2) Sia m1 tale che m=dm1 , e sia c una soluzione dell’equazione congruenziale ax ≡ b (mod m). Allora l’insieme delle soluzioni di tale equazione congruenziale coincide con .
Dimostrazione
(1) Dalle ipotesi segue che b=db1= (au+mv)b1 =aub1 + mvb1 ≡ aub1 (mod m)
⇒ ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).
(2) Sia n una qualunque soluzione dell’equazione congruenziale ax ≡ b (mod m)
⇒ an ≡ b ≡ an (mod m)
⇒ m=dm1 è un divisore di ac-an=a(c-n)
⇒ se a1 è il numero intero tale che a=da1 , allora m1 è un divisore di a1(c-n)
⇒ m1 è un divisore di c-n (perché m1 e a1 sono coprimi)
⇒ n appartiene a .
Viceversa, sia r un elemento di
⇒ esiste un numero intero k tale che r=c+km1
⇒ ar = a(c+km1) = ac+akm1 ≡ ac ≡ b (mod m)
⇒ r è soluzione dell’equazione congruenziale ax ≡ b (mod m).
Definizione 4.5
Siano m1 , … , mt numeri interi maggiori di 1. Se a1 , … , at , b1 , … , bt sono numeri interi, l’insieme
{ a1x ≡ b1 (mod m1) , … , atx ≡ bt (mod mt) } si chiama sistema di equazioni congruenziali lineari e si indica con il simbolo
Definizione 4.6
Si dice che un numero intero c è soluzione del sistema di equazioni congruenziali
se c è soluzione di ciascuna equazione congruenziale aix ≡ bi (mod mi).
Teorema 4.6 (Teorema Cinese del Resto)
Siano m1 , … , mt numeri interi maggiori di 1 e siano b1 , … , bt numeri interi.
Si supponga che m1 , … , mt siano a due a due coprimi. Allora
(1) si ponga per ciascun i=1,…,t , , e sia ci un numero intero tale che
; ne segue che
è soluzione del sistema
(2) Se c è soluzione di tale sistema, allora l’insieme delle soluzioni del sistema coincide con .
Dimostrazione
(1) Sia h un qualunque elemento dell’insieme {1,…,t}, e si consideri l’equazione x≡bh (mod mh).
Allora bh m’h ch ≡ bh (mod mh) (perché m’h ch ≡1 (mod mh); d’altra parte, per ciascun j≠h, bj m’j cj ≡0 (mod mh)
è soluzione dell’equazione x≡bh (mod mh) .
(2) Sia n una qualunque soluzione del sistema di equazioni congruenziali
⇒ per ciascun i=1,…,t si ha che c≡n (mod mi ) e quindi mi è un divisore di c-n
⇒ dunque m1∙…∙mt è un divisore di c-n e quindi n appartiene a .
Viceversa, sia r un qualunque elemento di
⇒ r≡c (mod m1∙…∙mt) e quindi per ciascun i=1,…,t si ha che r ≡c (mod mi )
⇒ per ciascun i=1,…,t si ha che r≡bi (mod mi )
⇒ r è soluzione del sistema di equazioni congruenziali.
La prima formulazione originale del teorema è contenuta in un libro, scritto nel III secolo, del matematico cinese Sun Zi; il teorema è stato successivamente inserito in un libro scritto da Qin Jiushao nel 1247.
Il Teorema Cinese del Resto verrà applicato diverse volte nel seguito.
Nella prossima slide verrà presentata una prima applicazione del Teorema Cinese del Resto: utilizzando tale teorema si fornirà una caratterizzazione, che risulterà molto utile in seguito, del valore che la funzione di Eulero assume per un numero che sia prodotto di due interi coprimi.
Teorema 4.7
Siano n1 ,n2 numeri interi maggiori di 1. Se n1 e n2 sono coprimi, allora φ(n1n2)=φ(n1)φ(n2).
Dimostrazione
Siano X1 ={ bє N | 1≤b≤n1 , (b,n1)=1}, e X2 ={ bє N | 1≤b≤n2 , (b,n2)=1}.
Sia poi X= { bє N | 1≤b≤n1n2 , (b,n1n2)=1}.
Allora |X1|=φ(n1) , |X2|=φ(n2) , |X|=φ(n1n2).
Se b è un qualunque elemento di X, allora b è coprimo con n1n2 , sicché per ciascun i=1,2, il resto della divisione euclidea di b per ni è coprimo con ni , e quindi appartiene a Xi .
Si consideri la funzione f:X → X1 x X2 definita ponendo f(b)=(r1 , r2), dove ri è il resto delle divisione euclidea di b per ni .
Sia (b1 , b2) un qualunque elemento di X1 x X2 , e si consideri il sistema di equazioni congruenziali
Per il Teorema Cinese del Resto, esiste una soluzione b di tale sistema tale che 0≤b≤n1n2 .
Per ciascun i=1,2, (bi ,ni)=1 e quindi (b,n1n2)=1 ⇒ b appartiene a X.
D’altra parte, e 1≤bi ≤ni -1⇒ bi è il resto delle divisione euclidea di b per ni f(b)=(b1 , b2). Dunque f è suriettiva.
Siano ora b,c elementi di X tali che f(b)=f(c)=(r1 , r2)
⇒ b e c sono soluzioni del sistema di equazioni congruenziali
⇒ per il Teorema Cinese del Resto, b=c (perché 1≤b≤n1n2-1 e 1≤b≤n1n2-1). Dunque f è iniettiva.
Dalla biettività di f segue che |X|=|X1 x X2|, e quindi l’asserto.
Prposizione 4.8
(1) Se p e q sono primi positivi distinti, è possibile determinare φ(pq), partendo da p e q, con complessità
O((log p)(log q)).
(2) Se n è un numero naturale prodotto di due primi distinti, è possibile determinare i primi, partendo da n e φ(n), con complessità O((log n)3).
Dimostrazione
(1) Calcolare φ(pq)= (p-1)(q-1) ha complessità O((log p)(log q)).
(2) Siano p1 e p2 i due primi da determinare
⇒ p1 p2=n e p1+p2 = n-φ(n)+1.
Si ponga b=n-φ(n)+1
⇒ p1 e p2 sono le due soluzioni dell’equazione x2-bx+n=0
⇒ p1 e p2 si calcolano con la formula , e tale calcolo (partendo da n e φ(n) ) ha complessità O((log n)3).
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