Anteprima
Vedrai una selezione di 27 pagine su 126
Test di primalità probabilistici e deterministici Pag. 1 Test di primalità probabilistici e deterministici Pag. 2
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 6
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 11
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 16
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 21
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 26
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 31
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 36
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 41
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 46
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 51
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 56
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 61
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 66
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 71
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 76
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 81
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 86
Anteprima di 27 pagg. su 126.
Scarica il documento per vederlo tutto.
Test di primalità probabilistici e deterministici Pag. 91
1 su 126
Disdici quando vuoi 162x117
Disdici quando
vuoi
Acquista con carta
o PayPal
Scarica i documenti
tutte le volte che vuoi
Sintesi

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.

Estratto del documento

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

Dettagli
126 pagine