Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Laurea in Informatica
La matematica si è sempre interessata allo studio dei numeri primi, cercando di evidenziarne le proprietà e accentuarne le differenze con gli altri numeri inteti, detti composti.
Oggi, molte di queste caratteristiche sono ancora da formalizzare e rimangono delle congetture. Recentemente è stato risolto un problema, noto in letteratura come "PRIMES" e che consiste nel trovare un algoritmo efficiente per testare la primalità di un numero. In realtà , l'interesse sull'efficienza computazionale si è diffuso solo negli anni sessanta con l'avvento dei calcolatori elettronici, ma da parecchi secoli, i matematici si sono cimentati nella produzione di algoritmi di primalità più o meno veloci.
CAPITOLO 1. RICHIAMI DI ALGEBRA 21
∗
Teorema 25 (Teorema del logaritmo discreto). Se g è un generatore di Z allora
n
x y
l’equazione g ≡ g (mod n) vale se e solo se vale l’equazione x ≡ y (mod φ(n)).
x y
Dimostrazione. Necessità : g ≡ g (mod n) ⇒ x ≡ y (mod φ(n))
Poichè la sequenza di potenze di g genera ogni elementro di [g] e | [g] |= ord(g) = φ(n),
la sequenza di g è periodica con periodo φ(n) . Quindi y = x + kφ(n) o x = y + kφ(n)
con k ∈ N. In ogni caso, segue la tesi. x y
Sufficienza : x ≡ y (mod φ(n)) ⇒ g ≡ g (mod n)
Se x ≡ y (mod φ(n)) allora, x = y + kφ(n) per qualche k ∈ Z. Quindi :
x y+kφ(n) y (φ(n)) k y k y
g ≡ g (mod n) ≡ g · (g ) (mod n) ≡ g · 1 (mod n) ≡ g (mod n).
a a
Teorema 26. Sia n = p · · · p un numero intero dispari, e siano y ∈ Z tale che
1 r
r
1
+ k
gcd(y, n) = 1 e k ∈ N . La congruenza, x ≡ y (mod n) ha una soluzione se e solo se
a ∗
)) divide ord (y) ∀i : 1 ≤ i ≤ r con g generatore di Z . Se la congruenza
gcd(k, φ(p i g i ai
i i p
i
ha una soluzione, allora ci sono esattamente
Y a ))
gcd(k, φ(p i
i
1≤i≤r
soluzioni distinte modulo n. k k
Dimostrazione. La congruenza x ≡ y (mod n) è equivalente a scrivere il sistema x ≡ y
a
(mod p ) per ogni divisore primo p con 1 ≤ i ≤ r. Dal Teorema del logaritmo discreto
i i
i a
le congruenze possono essere scritte nella forma k · ord (x) ≡ ord (y) (mod φ(p )).
i
g g i
i i a
Ognuna di queste congruenze ammette una soluzione se e solo se d = gcd(k, φ(p ))
i
i i
divide ord (y) per ogni i.
g i k
Consideriamo una soluzione x dell’equazione x ≡ y (mod n). Poichè gcd(y, n) = 1
0 k k −1
allora esiste l’inverso moltiplicativo di x modulo n. Sia esso (x ) . A questo punto,
0 0
−1 −1
k k −1 k k k
per ogni altra soluzione x di x (x ) = x (x ) ≡ 1 (mod n) ovvero (xx ) ≡ 1
0 0 0
a
(mod p ) per ogni 1 ≤ i ≤ r e dal teorema del logaritmo discreto:
i
i a
−1
k · ord (xx ) ≡ 0 (mod φ(p )) ∀1 ≤ i ≤ r
i
g 0 i
i
CAPITOLO 1. RICHIAMI DI ALGEBRA 22
−1
Notiamo che se ord (xx ) = 0 la conguenza sopra indicata è vera. Pertanto ciascuna
g 0
i
di queste r equazioni ha esattamente d soluzioni
i a
φ(p )
i
−1 i
) = 0 + t dove t = 0, 1, ..., d − 1
ord (xx i i i
g 0
i d i a
−1
Adesso, ogni r-pla di soluzioni per il sistema di equazioni k·ord (xx ) ≡ 0 (mod φ(p ))
i
g 0 i
i k
per ogni 1 ≤ i ≤ r, rappresenta una soluzione dell’equazione x ≡ y (mod n). Ma il
Q
ri=1
numero di r-ple è d . Segue la tesi.
i 2
Corollario 4. Se p è un numero primo dispari ed a ≥ 1, allora l’equazione x ≡ 1
a
(mod p ) ha solo due soluzioni, x = 1 e x = −1.
∗
Dimostrazione. Sappiamo che Z è ciclico ed ha generatore g. Per il lemma precendente,
a
p
a 2 a
poichè gcd(2, φ(p )) = 2 e 2 | ord (1) = 0, l’equazione x ≡ 1 (mod p ) ammette
g
esattamente 2 soluzioni. Per verifica diretta possiamo notare che le soluzioni sono 1 e
-1.
Definizione 22. Un numero x è una radice quadrata non banale di 1 modulo n, se
2
soddisfa l’equazione x ≡ 1 (mod n) con x 6 = 1 e x 6 = −1.
Teorema 27. Se esiste una radice quadrata non banale di 1 modulo n, allora n è
composto.
Dimostrazione. Per assurdo, se n fosse primo, per il corollario precedente, l’equazione
2
x ≡ 1 (mod n) ammetterebbe due sole soluzioni x = 1 e x = −1 e quindi nessuna
soluzione non banale.
Lemma 3. Se p è un numero primo e a un intero qualsiasi non divisibile per p, allora
esiste un unico intero b ∈ {1, 2, ..., p − 1} tale che ab ≡ 1 (mod p).
Dimostrazione. Moltiplichiamo i numeri 1, 2, ..., p−1, per a e consideriamo i resti r , r , ..., r
1 2 p−1
che si ottengono dividendo ciascun prodotto per p. Supponiamo per assurdo che r = r
i j
per qualche i > j. Allora ai ≡ aj (mod p) e quindi a(i − j) ≡ 0 (mod p). Cioè p deve
dividere a(i − j). Ma p non può dividere a (per ipotesi), né i − j, perchè i e j sono interi
CAPITOLO 1. RICHIAMI DI ALGEBRA 23
positivi minori di p e quindi 0 < i − j < p. Quindi tutti i numeri r sono distinti, ed uno
i
di questi è necessariamente uguale ad 1.
Teorema 28 (Wilson). Un intero p è primo se e solo se (p − 1)! ≡ −1 (mod p).
Dimostrazione. Necessità : Per p = 2, 3 il risultato è ovvio. Supponiamo dunque p ≥ 5
e consideriamo il prodotto (p − 1)! = 1 · 2 · · · (p − 1). Dal Lemma 3, possiamo associare
a ciascun intero 2 ≤ a ≤ p − 2 il suo inverso moltiplicativo b ∈ {1, 2, ..., p − 1} che è
∗
unico e diverso da a. Infatti, i soli elementi di Z che sono uguali al proprio inverso
p
∗
moltiplicativo in Z sono 1 e p − 1. Questo ci assicura che (p − 1)! ≡ 1 · (p − 1) (mod p)
p
e quindi (p − 1)! ≡ −1 (mod p),
Sufficienza : Supponiamo per assurdo che p sia composto, cioè che esiste un intero
1 < d < p − 1 tale che d | p. Allora d | (p − 1)!. Poichè, per ipotesi, p | (p − 1)! + 1, allora
d | (p − 1)! + 1, ma d | (p − 1)! e pertanto d = 1. Assurdo.
Teorema 29. Siano k, m ∈ Z tali che gcd(k, m) = 1. Se {a , a , ..., a } è un insieme di
1 2 m
residui incongruenti modulo m allora anche {ka , ka , ..., ka } è un insieme di residui
1 2 m
incongruenti modulo m.
Dimostrazione. Per ipotesi sappiamo che a 6≡ a (mod m) ∀i, j : 1 ≤ i < j ≤ m. Se
i j
per assurdo, esistessero f, g con 1 ≤ f < g ≤ m tali che ka ≡ ka (mod m), allora
g
f
m | k(a − a ) e poichè gcd(m, k) = 1 si avrebbe a ≡ a (mod m), assurdo.
g g
f f ∗
Corollario 5. Siano k, m ∈ Z tali che gcd(k, m) = 1. Se Z = {a , a , ..., a } è
1 2 φ(m)
m
l’insieme completo dei residui primi modulo m, allora anche {ka , ka , ..., ka } è un
1 2 φ(m)
insieme completo di residui primi modulo m.
1.4 Cenni sulla teoria dei polinomi
Definizione 23 (funzione polinomiale). Sia K un qualunque campo, definiamo funzione
polinomiale su K, una funzione p : K → K, tale che ∃n ∈ N e degli elementi a ∈ K
i
0 1 n
tali che p(α) = a α + a α + ... + a α , per ogni α ∈ K.
0 1 n
CAPITOLO 1. RICHIAMI DI ALGEBRA 24
Detto F l’insieme di tutte le funzioni polinomiali di K in se stesso, è possibile definire
in tale insieme la somma e il prodotto, tenendo conto della definizione di somma e
prodotto nel campo K: (p + q)(x) = p(x) + q(x), ∀x ∈ K
(p · q)(x) = p(x) · q(x), ∀x ∈ K.
In tal modo F assume le caratteristiche di anello commutativo. Due funzioni polinomiali
sono uguali se assumono gli stessi valori in corrispondenza di ogni x ∈ K. L’elemento
neutro (lo zero) rispetto alla somma, è quella funzione polinomiale che associa ad ogni
x ∈ K l’elemento neutro di K. La funzione unità di F è la funzione polinomiale che
associa ad ogni x ∈ K, l’elemento unità di K, ossia la funzione costante uguale ad 1.
Definizione 24 (polinomio). Un polinomio p(x) a coefficienti nel campo K, è un’e-
spressione del tipo : 2 n
p(x) = a + a x + a x + ... + a x
0 1 2 n
con a ∈ K e x un’indeterminata. L’insieme dei polinomi in K si indica con il simbolo
i
K[x].
I concetti di polinomio e funzione polinomiale, sono chiaramente diversi. Definita
2
l’applicazione φ : K[x] → F che associa ad ogni polinomio p(x) = a + a x + a x +
0 1 2
n
... + a x ∈ K[x] la funzione polinomiale p(x) che per ogni c ∈ K manda in p(c) =
n 2 n
a + a c + a c + ... + a c ∈ K, in generale è suriettiva ma non è iniettiva. Può
0 1 2 n
accadere, infatti, che due polinomi diversi danno luogo alla stessa funzione polinomiale.
Definizione 25 (grado di un polinomio). Per grado di un polinomio p(x) = a + a x +
0 1
2 n
a x + ... + a x , si intende l’intero n se a 6 = 0.
2 n n
Il grado del polinomio p(x) lo denotiamo con deg(p) e a è detto coefficiente direttivo.
n
Un polinomio che ha il coefficiente direttivo pari ad 1 è detto monico.
Le relazioni fra i gradi di due polinomi e quelli della loro somma e del loro prodotto sono
le seguenti:
deg((p + q)) ≤ max(deg(p), deg(q)) deg(p · q) = deg(p) + deg(q) (purchè p, q 6 = 0).
CAPITOLO 1. RICHIAMI DI ALGEBRA 25
Teorema 30. Siano f (x), g(x) ∈ K[x], con g(x) monico. Allora esistono e sono unici
due polinomi q(x), r(x) ∈ K[x] tali che:
f (x) = g(x)q(x) + r(x)
con deg(r) < deg(g).
Dimostrazione. 0 0
Unicità : Supponiamo che f (x) = g(x)q(x) + r(x) = g (x)q(x) + r (x), con deg(r) <
0 0 0 0
deg(g) , deg(r ) < deg(g) e q(x) 6 = q (x). Allora r(x)−r (x) = g(x)(q (x)−q(x)) e quindi:
0 0 0 0
deg(g) + deg(q − q) = deg(g(q − q)) = deg(r − r ) ≤ max{deg(r), deg(r )} < deg(g)
0 0
e ciò è assurdo. Pertanto q(x) = q (x) e quindi r(x) = r (x).
Esistenza : Il caso f (x) = 0 è banale. Procediamo allora per induzione sul grado di f (x).
Se deg(f ) = 0, allora f (x) = g(x) · 0 + f (x) è la divisione richiesta, purchè deg(g) > 0.
Se anche deg(g) = 0, abbiamo g(x) = 1 e quindi f (x) = 1 · f (x) + 0. Supponiamo
deg(f ) = n > 0 e che la tesi sia vera per i polinomi di grado minore di n. Indichiamo
con m il grado di g.
Se n < m, allora f (x) = g(x) · 0 + f (x) è la divisione richiesta.
n n−m
Se n ≥ m, scriviamo f (x) = a + a x + ... + a x e consideriamo h(x) = a x . Allora
0 1 n n
il polinomio f (x) = f (x) − g(x)h(x) ha grado minore di n : infatti g(x)h(x) ha grado
1
n ed ha lo stesso coefficiente direttivo di f (x). Per l’ipotesi induttiva, possiamo scrivere
f (x) = g(x)q (x) + r(x), con deg(r) < deg(g). Ma allora
1 1
f (x) = g(x)h(x) + f (x) = g(x)h(x) + g(x)q (x) + r(x) = g(x)(h(x) + q (x)) + r(x),
1 1 1
e si ha la tesi.
Se f (x) = g(x)h(x), si dice che f (x) è divisibile per g(x), oppure g(x) divide f (x) in
K[x]. Si può altresi dimostrare il seguente teorema :
Teorema 31 (Esistenza e unicità del massimo comune divisore). Sia K un campo e siano
f (x), g(x) ∈ K[x] due polinomi non nulli. Allora esiste un unico polinomio monico d(x)
tale che :
CAPITOLO 1. RICHIAMI DI ALGEBRA 26
1. d(x) divide f (x) e g(x);
2. ogni divisore comune di f (x) e g(x) divide d(x). Inoltre esistono due polinomi
h(x), k(x) ∈ K[x] tali che
d(x) = h(x)f (x) + k(x)g(x) (identità di Bezout per i polinomi).
Tale polinomio monico d(x) si chiama massimo comune divisore di f (x) e g(x) e
si scrive d(x) = gcd(f (x), g(x)).
Definizione 26. Se f (x) ∈ K[x], un elemento a ∈ K si dice che è una radice o zero di
f (x) se risulta f (a) = 0.
Teorema 32 (Ruffini). Se f (x) ∈ K[x] ed a ∈ K, a è una radice di f (x) ⇔ (x−a) | f (x)
Dimostrazione.
Necessità : Dividiamo f (x) per (x − a), si ha : f (x) = (x − a)q(x) + r(x), con deg(r) = 0.
Essendo a radice di f (x) otteniamo 0 = f (a) = 0q(a) + r(a) = r(a) e quindi r(x) = 0,
da cui (x − a) | f (x).
Sufficienza : Se (x − a) | f (x) si ha f (x) = (x − a)q(x). Sostituendo ad x il valore di a
otteniamo f (a) = 0, cioè a è radice di f (x).
Corollario 6. Un polinomio f (x) ∈ K[x] di grado n ≥ 0 ha al più n radici.
Dimostrazione. Dimostriamo il teorema per induzione su n.
Caso base : se n = 0, allora f (x) è costante e non ha radici.
Passo induttivo : se n > 0, allora f (x) o non ha radici e il teorema è vero, oppure ha
una radice a e, per il teorema di Ruffini, si ha f (x) = (x − a)q(x) in cui q(x) ha grado
n − 1. Poichè le radici di f (x) sono a e le radici di q(x), per ipotesi induttiva, sono al
più n − 1, segue che f (x) ha al più n radici.
Definizione 27 (Riducibilità). Sia f (x) ∈ K[x] un polinomio tale che deg(f ) ≥ 2. Si
dice che f (x) è riducibile in K[x] se esistono g(x) e h(x) non costanti (cioè di grado
maggiore o uguale ad uno) tali che f (x) = g(x) · h(x).
CAPITOLO 1. RICHIAMI DI ALGEBRA 27
Definizione 28. Si dice che f (x) è irriducibile in K[x] se non è costante e non esistono
g(x) e h(x) ∈ K[x] con deg(g) ≥ 1 e deg(h) ≥ 1 tali che f (x) = g(x) · h(x).
Definizione 29. Sia p(x) ∈ K[x] un polinomio di grado n. Diciamo che due polinomi
f (x) e g(x) sono congrui modulo p(x) in K[x] e scriveremo
f (x) ≡ g(x) (mod p(x)) in K[x]
se esiste un opportuno polinomio h(x) ∈ K[x] tale che f (x) − g(x) = h(x) · p(x).
In particolare useremo la notazione f (x) ≡ g(x) (mod p(x), n) per indicare che
f (x) ≡ g(x) (mod p(x)) in Z [x], e la notazione f (x) ≡ g(x) (mod n) per indicare
n