Algebra Computazionale - UniTrentodegraaf/compalg/alg_comp.pdf · 1.1.4 Algoritmo di divisione con...

Algebra Computazionale

Serena Cicalo

Willem de Graaf

Indice

1 Basi di Grobner 11.1 Basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Anelli polinomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Il caso di polinomi in una variabile . . . . . . . . . . . . . . . . . . . . 21.1.3 Ordini monomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.4 Algoritmo di divisione con resto . . . . . . . . . . . . . . . . . . . . . 41.1.5 Ideali monomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.6 Basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.1.7 Calcolare basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Applicazioni di basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2.1 Risolvere equazioni polinomiali . . . . . . . . . . . . . . . . . . . . . . 151.2.2 Applicazioni di basi di Grobner in geometria . . . . . . . . . . . . . . 171.2.3 Polly-cracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Fattorizzazione di numeri interi in fattori primi 252.1 Fattorizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.1.1 Metodo di Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.1.2 Basi di fattori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.3 Frazioni continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1.4 Fattorizzazione con frazioni continue . . . . . . . . . . . . . . . . . . . 312.1.5 Curve ellittiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.1.6 Fattorizzazione con curve ellittiche . . . . . . . . . . . . . . . . . . . . 372.1.7 Complessita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Fattorizzazione di polinomi 433.1 Alcuni fatti generali sui polinomi . . . . . . . . . . . . . . . . . . . . . . . . . 433.2 L’algoritmo di Berlekamp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.3 Algoritmo di Cantor-Zassenhaus (1981) . . . . . . . . . . . . . . . . . . . . . 483.4 Fattorizzazione di polinomi in Q . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.4.1 Sollevamento di Hensel . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.4.2 Sollevamento di Hensel per piu fattori . . . . . . . . . . . . . . . . . . 56

3.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Capitolo 1

Basi di Grobner

1.1 Basi di Grobner

1.1.1 Anelli polinomiali

Sia k indichiamo un campo. Indichiamo con k[x1, . . . , xn] l’anello polinomiale in n variabili,cioe

k[x1, . . . , xn] = {∑

i1,...,in

ci1...inxi11 · · · xin

n | ci1...in ∈ k}.

Esempio 1.1.1 In una variabile scriviamo k[x], in due variabili scriviamo k[x, y] e in trevariabili k[x, y, z].

Se α = (α1, . . . , αn), αi ∈ Z, scriviamo xα = xα1

1 · · · xαnn . Questo elemento e chiamato

monomio.

Esempio 1.1.2 Abbiamo che x2yz10 e un monomio. Invece 2x2y + 3yz e un polinomio.

In generale un polinomio puo essere scritto come∑

α cαxα.

Un anello R si dice commutativo se e un anello e fg = gf per ogni f, g ∈ R.

Definizione 1.1.3 Sia R un anello commutativo. Un sottoinsieme I ⊂ R e chiamato idealese

- 0 ∈ I;

- se f, g ∈ I anche f + g ∈ I;

- se f ∈ I e g ∈ R allora gf ∈ I.

Nella teoria delle basi di Grobner avremo a che fare solamente con anelli polinomiali.Quindi R = k[x1, . . . , xn].

Siano f1, . . . , fs ∈ k[x1, . . . , xn] e poniamo

I = {s∑

i=1

gifi | gi ∈ k[x1, . . . , xn]}.

Allora I e un ideale di k[x1, . . . , xn]. Questo si vede facilmente.

2 Basi di Grobner

Vedremo piu avanti che ogni ideale di k[x1, . . . , xn] e di questa forma.

Notazione. Indichiamo I con I = 〈f1, . . . , fs〉 e diciamo che I e generato da f1, . . . , fs.

Problema fondamentale: “Dato I = 〈f1, . . . , fs〉 e g ∈ k[x1, . . . , xn] determinare se g ∈ I”.

Esempio 1.1.4 Sia R = k[x, y, z], f1 = xyz − xy, f2 = x2y − yz e g = yz2 − yz. Vogliamovedere se g ∈ 〈f1, f2〉 o meno.

Si ha che

xf1 − zf2 = −x2y + yz2

quindi aggiungendo f2 si trova

xf1 − zf2 + f2 = yz2 − yz = g

dunque g = xf1 + (1 − z)f2 ∈ 〈f1, f2〉.

Esempio 1.1.5 Sia I ⊂ k[x, y, z] l’ideale generato da f1 = x2yz−yz−x, f2 = xy2z−xy−y,f3 = xyz2 − xy − z. Si puo provare che x2 − z2 e y − z sono elementi di I. Ma certamentenon e molto ovvio.

Si vede che provare che f ∈ 〈f1, . . . , fs〉 puo essere abbastanza complicato. Ma almenosappiamo che dobbiamo trovare hi tali che f =

∑i hifi. Provare che f 6∈ 〈f1, . . . , fs〉 sembra

ancora piu complicato.

1.1.2 Il caso di polinomi in una variabile

Lemma 1.1.6 Sia I ⊂ k[x] un ideale. Allora esiste un h ∈ k[x] tale che I = 〈h〉.

Dimostrazione. Sia h un elemento non nullo di grado minimo in I. Sia f ∈ I. Alloraf = qh+ r con q, r ∈ k[x] e deg(r) < deg(h).

Poiche r = f−qh ∈ I segue che r = 0 in quanto h e di grado minimo in I. Quindi f = qh.�

Adesso sia I = 〈h〉 ⊂ k[x] e f ∈ k[x]. Abbiamo la seguente procedura per verificare sef ∈ I o meno:

1) Si scrive f = qh+ r con deg(r) < deg(h). (Divisone con resto.)

2) Se r = 0 allora f ∈ I altrimenti f 6∈ I.

La prova del Lemma 1.1.6 dimostra che questa procedura funziona. (Osserviamo che se Ie generato da h allora h e un elemento di I di grado minimale.)

Vorremo trovare qualcosa di analogo nel caso di piu variabili. Nel caso di una variabileusiamo un ordine sui monomi xm < xn se m < n. Su questo si basa la divisione con resto.Per piu variabili facciamo una cosa analoga.

1.1 Basi di Grobner 3

1.1.3 Ordini monomiali

Ricordiamo che xα = xα1

1 · · · xαnn dove α = (α1, . . . , αn).

Definizione 1.1.7 Un ordine ≤ sull’insieme {xα} dei monomi di k[x1, . . . , xn] e chiamatoordine monomiale se

1) ≤ e totale, cioe per ogni α, β abbiamo xα ≤ xβ oppure xβ ≤ xα e quindi due elementi sonoconfrontabili.

2) ≤ e moltiplicativo, cioe se xα ≤ xβ allora xαxγ ≤ xβxγ per ogni γ.

3) Non ci sono catene infinite discendenti xα(1) > xα(2) > . . ..

Scriviamo N = Z≥0. Possiamo identificare {xα | α ∈ Nn} e Nn tramite xα ↔ α.Quindi se ≤ e un ordine monomiale, otteniamo un ordine su Nn con α < β se xα < xβ.Allora le condizioni per essere un ordine monomiale diventano:

1) ≤ e totale.

2) Se α ≤ β allora α+ γ ≤ β + γ per ogni γ.

3) Non ci sono catene infinite discendenti.

Nel seguito, quando parliamo di un ordine monomiale, a volte usiamo l’ordine sui monomi,e a volte su Nn, secondo quale e il piu conveniente.

Spesso la seguente osservazione e utile.

Lemma 1.1.8 Poniamo γ0 = (0, . . . , 0) ∈ Nn e sia < un ordine monomiale. Allora α > γ0

per ogni α ∈ Nn, α 6= γ0.

Dimostrazione. Se α < γ0 allora α + α < α + γ0 = α. Nello stesso modo troviamo che(k + 1)α < kα. Quindi abbiamo trovato una catena discendente infinita, che e una contrad-dizione. �

Esempio 1.1.9 (Ordine lessicografico). Si indica con <lex. Si ha che α <lex β se αi < βi

dove i e minimale con αi 6= βi.Per esempio in k[x, y, z] abbiamo che

xy2z100 <lex x2yz

exyz <lex xy

3.

Dimostriamo ora che <lex e un ordine monomiale.Dimostrazione. Per provare che <lex e monomiale bisogna controllare che verifichi le treproprieta. Si ha:

1) E’ totale. Questo e ovvio perche se α 6= β esiste i con αi 6= βi.2) Se α <lex β e i minimale con αi 6= βi e quindi αi < βi. Allora i e ancora minimale con

(α+ γ)i 6= (β + γ)i e(α+ γ)i = αi + γi < βi + γi = (β + γ)i.

4 Basi di Grobner

Quindi (α+ γ) <lex (β + γ).3) Sia α(i) per i ≥ 1 con α(1) >lex α(2) >lex . . . una catena discendente infinita. Usiamo

l’induzione su n (n e il numero di variabili) per trovare una contraddizione.Se n = 1 e ovvio che non esistano catene discendenti infinite.Assumiamo che non ci siano catene discendenti infinite per n − 1 variabili (sempre con

<lex).Osserviamo che 0 ≤ α(i)1 ≤ α(1)1.Quindi

{α(i) | i ≥ 1} =

α(1)1⋃

k=0

Ck

dove Ck = {α(i) | i ≥ 1, α(i)1 = k}.Quindi almeno un Ck0

deve essere infinito.Allora facciamo Ck0

= {(α2, . . . , αn) | α ∈ Ck0}.

Questa e una catena discendente infinita per <lex con n − 1 variabili. Quindi abbiamouna contraddizione. �

Esempio 1.1.10 (Ordine lessicografico graduato). Si indica con <glex.Sia |α| = α1 + . . .+ αn. Questo e il grado del monomio xα. Definiamo α <glex β se

- |α| < |β|- oppure |α| = |β| e α <lex β.

E’ ovvio che <glex e un ordine monomiale.

1.1.4 Algoritmo di divisione con resto

Sia f =∑

α cαxα ∈ k[x1, . . . , xn] e sia ≤ un ordine monomiale fissato. Sia α massimale per

l’ordine ≤ con cα 6= 0. Allora xα e chiamato monomio di testa di f e denotato con LM(f)(per “leading monomial”), mentre cα e chiamato coefficiente di testa di f e denotato conLC(f).

Fissiamo un ordine monomiale ≤ su R = k[x1, . . . , xn]. Per f ∈ R indichiamo con LM(f)il monomio di testa e con LC(f) il coefficiente di testa di f .

Algoritmo 1.1.11 Dati: f1, . . . , fs ∈ R, g ∈ R.Calcoliamo: r ∈ R tale che g = h1f1 + . . .+ hsfs + r con hi ∈ R e nessun monomio di r

e divisibile per un LM(fi).

1) Poniamo g = g, r = 0;

2) Se g = 0 ci fermiamo;

3) Sia xγ = LM(g), c = LC(g). Se esiste fi tale che LM(fi) divide xγ allora poniamo

g = g − c

LC(fi)xβfi

dove xβLM(fi) = xγ . Altrimenti poniamo

g = g − cxγ e r = r + cxγ .

Torniamo a 2).


Proposizione 1.1.12 L’algoritmo 1.1.11 termina correttamente.

Dimostrazione. Abbiamo che LM(g) diminuisce ad ogni passo. Quindi l’algoritmo terminasempre perche non ci sono catene discendenti infinite.

Inoltre abbiamo sempre che g − (g + r) ∈ I dove I = 〈f1, . . . , fs〉. Questo e sicuramentevero all’inizio (g = g, r = 0). Se e vero per g e r e

g1 = g − c

LC(fi)xβfi e r1 = r

allora

g − (g1 + r1) = g − (g + r) +c

LC(fi)xβfi

e quindi anche g − (g1 + r1) ∈ I.

Se invece g1 = g1 − cxγ e r1 = r + cxγ allora

g − (g1 + r1) = g − (g + r) ∈ I.

Segue che quando l’algoritmo termina si ha g = 0 e g − r ∈ I quindi

g − r = h1f1 + . . .+ hsfs.

Per costruzione si vede che nessun LM(fi) divide un monomio di r. �

Esempio 1.1.13 Siano f1 = xy+1, f2 = y+1 e g = xy−y. Consideriamo l’ordine monomiale<=<glex.

Possiamo procedere in due modi:

• Primo modo:

1) g = xy − y, r = 0;

2) g = g − f1 = −y − 1;

3) g = g + f2 = 0;

4) r = 0.

• Secondo modo:

1) g = xy − y, r = 0;

2) g = g − xf2 = −x− y;

3) g = g + x = −y, r = −x;4) g = g + f2 = 1;

5) g = g − 1 = 0, r = −x+ 1;

6) r = −x+ 1.

Si vede nell’Esempio che il resto dipende dalle scelte fatte durante l’algoritmo.

Vogliamo trovare un algoritmo che ci dia un resto unico che sia zero se e solo se g ∈ I =〈f1, . . . , fs〉.

6 Basi di Grobner

1.1.5 Ideali monomiali

Definizione 1.1.14 Sia A ⊆ Nn (possibilmente infinito). Allora l’ideale

I = 〈xα | α ∈ A〉 ⊂ R = k[x1, . . . , xn]

e chiamato ideale monomiale.

Lemma 1.1.15 Sia I = 〈xα | α ∈ A〉 un ideale monomiale. Allora h ∈ I se e solo se ognisuo monomio e in I.

Dimostrazione. “⇐”. Ovvio.“⇒”. Se h ∈ I allora h =

∑α∈A cαhαx

α con certi hα ∈ R e i cα ∈ k sono non nulli innumero finito.

Sia xγ un monomio di h quindi xγ e un monomio di almeno un hαxα. Ma

hα =

m∑

i=1

µixβ(i) =⇒ hαx

α =

m∑

i=1

µixβ(i)+α

quindi, per un certo i, abbiamo che

xγ = xβ(i)xα ∈ I.

�

Lemma 1.1.16 Le notazioni sono come nel lemma precedente. Si ha xγ ∈ I se e solo sexγ = xβxα per un certo β ∈ Nn e α ∈ A.

Dimostrazione. Analoga a quella del Lemma 1.1.15. �

Definiamo ora un ordine parziale � su Nn con α � β se αi ≤ βi per ogni i.

Esempio 1.1.17 Si ha (1, 2, 3) � (1, 3, 5). Oppure (1, 2, 3) � (1, 3, 2) e (1, 3, 2) � (1, 2, 3).

Quindi non tutti gli elementi sono confrontabili. Diciamo che α, β ∈ Nn con α � β eβ � α sono detti inconfrontabili.

Un insieme A ⊆ Nn che consiste solo di elementi inconfrontabili e chiamato anticatena.

Lemma 1.1.18 Un’anticatena in Nn e sempre finita.

Dimostrazione. Per n = 1 e ovvio perche � e uguale a ≤ sugli interi. (Quindi un’anticatenaha al massimo un elemento.)

Sia n > 1 minimale tale che esista un’anticatena infinita A ⊆ Nn. Prendiamo α ∈ A.Allora per ogni β ∈ A con β 6= α esiste i con βi < αi (e j con βj > αj), perche α e β nonsono confrontabili. Quindi

Ar {α} =

n⋃

i=1

{β ∈ A | βi < αi}.

Quindi poiche A e infinito, almeno un insieme Bi0 = {β ∈ A | βi0 < αi0} e infinito.Scriviamo δ = αi0 .


Allora Bi0 = ∪δ−1j=0{β ∈ A | βi0 = j}.

Quindi almeno uno di questi insiemi e infinito. Chiamiamolo C = {β ∈ A | βi0 = j0}.Poniamo

C ′ = {(β1, . . . , βj0−1, βj0+1, . . . , βn) | β = (β1, . . . , βn) ∈ C}.Ma anche C ′ e un’anticatena e |C ′| = |C| = ∞.

Poiche C ′ ⊆ Nn−1 abbiamo una contraddizione. �

Lemma 1.1.19 (Dickson) Sia A ⊆ Nn e I = 〈xα | α ∈ A〉 ⊂ R = k[x1, . . . , xn]. Alloraesiste A′ ⊂ A, con A′ finito e I = 〈xα | α ∈ A′〉.

In altre parole, un ideale monomiale e sempre generato da un numero finito di monomi.Dimostrazione. Sia B ⊆ A un’anticatena massimale (cioe non esiste un’anticatena B′ ⊆ Acon B′ ⊇ B e B′ 6= B). Per il Lemma 1.1.18 B e finito.

Osserviamo che per ogni α ∈ Nn l’insieme {β ∈ Nn | β � α} e finito.Poniamo A′ = B ∪⋃α∈B{β ∈ A | β � α}. Diciamo che I = 〈xα | α ∈ A′〉. L’inclusione

“(⊇)” e ovvia perche A′ ⊆ A. Per “(⊆)” sia β ∈ A. Dobbiamo provare che esiste γ e α ∈ A′

con xβ = xγxα.Se β ∈ B ⊆ A′ siamo apposto. Altrimenti, se β 6∈ B allora esiste α ∈ B con α e β

confrontabili (altrimenti B ∪ {β} sarebbe un’anticatena piu grande). Dunque ci sono duepossibilita: α � β oppure β � α.

Se α � β allora prendiamo γ = β−α e quindi xβ = xγxα. Se β � α allora β ∈ A′ e quindipossiamo prendere γ = (0, . . . , 0) e α = β. �

Teorema 1.1.20 Sia ≤ un ordine su Nn con

1) ≤ e totale.

2) Se α ≤ β allora α+ γ ≤ β + γ per ogni γ ∈ Nn.

3) α ≥ 0 = (0, . . . , 0) per ogni α ∈ Nn.

Allora ≤ e un ordine monomiale.

Dimostrazione. Bisogna provare che non ci sono catene discendenti infinite, oppure che seα(1) ≥ α(2) ≥ . . . e una catena infinita allora esiste un m con α(m) = α(m+1) = α(m+2) =. . ., cioe la catena diventa stabile. Allora supponiamo α(1) ≥ α(2) ≥ . . ..

Sia A = {α(i) | i ≥ 1} e I = 〈xα | α ∈ A〉. Per il Lemma di Dickson si ha che esisteA′ ⊂ A, A′ finito, con I = 〈xα | α ∈ A′〉.

Scriviamo A′ = {β(1), . . . , β(r)} con β(1) > β(2) > . . . > β(r). Diciamo che α(i) ≥ β(r)per ogni i.

Infatti, xα(i) ∈ I quindi per il Lemma 1.1.16 esiste β(j) e γ ∈ Nn con xα(i) = xγxβ(j)

oppure α(i) = γ + β(j).Per la 3) sappiamo che γ ≥ 0 = (0, . . . , 0) quindi

α(i) = γ + β(j) ≥ 0 + β(j) = β(j) ≥ β(r).

Sia m tale che α(m) = β(r). Visto che α(m) ≥ α(m + 1) ≥ . . . ≥ β(r) e α(m) = β(r)segue che α(m) = α(m+ 1) = . . .. �

8 Basi di Grobner

Teorema 1.1.21 (della base di Hilbert) Ogni ideale di R = k[x1, . . . , xn] e generato daun numero finito di elementi.

Dimostrazione. Sia I ⊂ R un ideale e J = 〈LM(f) | f ∈ I〉 l’ideale generato da tutti imonomi di testa di elementi di I (relativo ad un qualsiasi ordine monomiale fissato).

Il Lemma di Dickson implica che esistono g1, . . . , gs ∈ I con

J = 〈LM(gi) | 1 ≤ i ≤ s〉.

Questi generano I. Infatti, sia f ∈ I, allora mediante l’algoritmo di divisione con restotroviamo h1, . . . , hs ∈ R con f = h1g1 + . . .+ hsgs + r con r ∈ R tale che nessun monomio dir sia divisibile per un LM(gi).

Ma r = f −∑higi ∈ I quindi LM(r) e un elemento di J . Quindi esiste i tale che LM(gi)divide LM(r) (Lemma 1.1.16) ma questo non e possibile tranne nel caso in cui r = 0. Segueche f =

∑higi. �

Corollario 1.1.22 Se Ik, per k ≥ 1, sono ideali di R con I1 ⊆ I2 ⊆ I3 ⊆ . . . allora esiste mcon Im = Im+1 = Im+2 = . . ..

Dimostrazione. Sia J = ∪k≥1Ik che e un ideale di R. Il Teorema 1.1.21 implica che esistonog1, . . . , gs ∈ J con J = 〈g1, . . . , gs〉. Sia ki tale che gi ∈ Iki

e m = max(k1, . . . , ks). Quindig1, . . . , gs ∈ Im e quindi Im+i = Im perche Im ⊆ Im+i e dato e Im+i ⊆ J = Im. �

1.1.6 Basi di Grobner

Definizione 1.1.23 Sia I ⊂ R = k[x1, . . . , xn] un ideale. L’ideale 〈LM(f) | f ∈ I〉 e chia-mato ideale iniziale di I e scriviamo 〈LM(I)〉 = 〈LM(f) | f ∈ I〉.

Definizione 1.1.24 Sia I ⊂ R = k[x1, . . . , xn] un ideale e G ⊂ I con 〈LM(I)〉 = 〈LM(g) | g ∈ G〉.Allora G e chiamato base di Grobner di I.

Osservazione 1.1.25• G = I e una base di Grobner di I.• Dalla prova del Teorema della base di Hilbert segue immediatamente che ogni ideale I

ha una base di Grobner finita.

Lemma 1.1.26 Sia I ⊆ k[x1, . . . , xn] un ideale. Allora un G ⊂ I e una base di Grobner diI se e solo se per ogni f ∈ I esiste g ∈ G tale che LM(g) divide LM(f).

Dimostrazione. Si ha che G e una base di Grobner di I se e solo se

〈LM(g) | g ∈ G〉 = 〈LM(I)〉

quindi se e solo se per ogni f ∈ I esiste g ∈ G tale che LM(g) divide LM(f) (Lemma 1.1.16). �

Proposizione 1.1.27 Sia I ⊂ R = k[x1, . . . , xn] un ideale e G ⊂ I una base di Grobner. Siaf ∈ R e r ∈ R un resto ottenuto con l’algoritmo di divisione con resto con f ∈ G. Allora r eunico, cioe non dipende dalle scelte fatte nell’algoritmo. Inoltre r = 0 se e solo se f ∈ I.


Dimostrazione. Supponiamo che

f = h1gi1 + . . .+ hsgis + r1 = h1gj1 + . . .+ htgjt + r2

con gik e gjkin G e ri ∈ R con la proprieta che nessun monomio di questi resti sia divisibile

per un LM(g) con g ∈ G.Segue che

r1 − r2 = h1gi1 + . . .+ hsgis + −h1gj1 − . . .− htgjt ∈ Iquindi per il Lemma 1.1.26 esiste g ∈ G tale che LM(g) divide LM(r1 − r2). Ma LM(r1 − r2)e un monomio di r1 oppure di r2 (o di entrambi). Segue che r1 − r2 = 0 e quindi r1 = r2.

Se f ∈ I allora r1 ∈ I (perche r1 = f −∑su=1 hugiu). Quindi esiste g ∈ G tale che LM(g)

divide LM(r1) (Lemma 1.1.26) e quindi r1 = 0. Per l’altra direzione: r1 = 0 implica f ∈ Ibanalmente. �

1.1.7 Calcolare basi di Grobner

Sia G ⊂ R = k[x1, . . . , xn] un sottoinsieme e f ∈ R. Fissiamo un ordine monomiale.Sia r ∈ R un resto ottenuto mediante la divisione con resto con G e f . Allora scriviamo

r = fG.Se fG = 0 si dice che f riduce a 0 modulo G.Siano f1, f2 ∈ Rr{0} e scriviamo xα(i) = LM(fi). Sia γ definito come γj = max(α(1)j , α(2)j).

Allora xγ e chiamato minimo comune multiplo di xα(1) e xα(2).Inoltre

S(f1, f2) =xγ

LC(f1)LM(f1)f1 −

xγ

LC(f2)LM(f2)f2

viene detto S-polinomio corrispondente a f1 e f2.

Esempio 1.1.28 Sia f1 = 2xyz2 −xy e f2 = 3x2y2z− 5xyz. Usiamo l’ordine <glex. Avremoche il minimo comune multiplo dei monomi di testa di f1 e f2 e xγ = x2y2z2 e

S(f1, f2) =xy

2(2xyz2 − xy) − z

3(3x2y2z − 5xyz) = −1

2x2y2 +

5

3xyz2,

quindi LM(S(f1, f2)) = x2y2.Si vede inoltre che il resto di S(f1, f2) modulo {f1, f2} non e zero perche x2y2 non e

divisibile da LM(f1) e LM(f2).In particolare l’insieme {f1, f2} non e una base di Grobner dell’ideale generato da f1, f2.

Un elemento della forma cxα con c ∈ k e chiamato termine.

Lemma 1.1.29 Sia G ⊂ R = k[x1, . . . , xn] e f ∈ R. Allora se f riduce a zero modulo G sipuo scrivere f = h1g1 + . . . + hsgs con gi ∈ G (non necessariamente diversi) e dove hi ∈ Rsono termini tali che

LM(f) = LM(h1g1) > LM(h2g2) > . . . > LM(hsgs).

Dimostrazione. Segue dall’algoritmo di divisione con resto. �

Il seguente teorema da un criterio con cui possiamo se un dato G ⊂ I e una base diGrobner o meno.

10 Basi di Grobner

Teorema 1.1.30 Sia I ⊂ R un ideale generato da G ⊂ I. Allora G e una base di Grobner

di I se e solo se S(g1, g2)G

= 0 per ogni g1, g2 ∈ G.

Dimostrazione.

“⇒” Se G e una base di Grobner, poiche S(g1, g2) ∈ I allora questo riduce a zero moduloG (Prposizione 1.1.27).

“⇐” Sia f ∈ I e proviamo che esiste g ∈ G tale che LM(g) divide LM(f). Allora con ilLemma 1.1.26 concludiamo che G e una base di Grobner di I.

Possiamo scrivere f = h1g1 + . . . + hsgs con hi ∈ R termini e gi ∈ G. Scriviamo mi =LM(higi) e m = m1 e assumiamo che

m = m1 = m2 = . . . = mv > mv+1 ≥ . . . ≥ ms.

Assumiamo che LC(gi) = 1 (se LC(gi) non e 1 la prova vale comunque ma la notazionediventa piu complicata).

Scegliamo un’espressione della forma f = h1g1 + . . . + hsgs con m minimale e tra questeuna con v minimale.

Supponiamo v > 1 e scriviamo hi = cixα(i). Quindi

f = c1xα(1)g1 + . . .+ csx

α(s)gs

= c1(xα(1)g1 − xα(2)g2) + (c1 + c2)x

α(2)g2 + . . .+ csxα(s)gs.

Adesso sia xγ il minimo comune multiplo di LM(g1) e LM(g2) e scriviamo xδ = m =LM(xα(1)g1) = LM(xα(2)g2). Quindi

xα(1)g1 − xα(2)g2 =xδ

LM(g1)g1 −

xδ

LM(g2)g2

perche xδ = xα(i)LM(gi).Quindi

xα(1)g1 − xα(2)g2 = xδ−γ

(xγ

LM(g1)g1 −

xγ

LM(g2)g2

)= xδ−γS(g1, g2).

Ma S(g1, g2) riduce a zero modulo G. Quindi per il Lemma 1.1.29

S(g1, g2) = u1gi1 + . . .+ utgit

dove ui e un termine e

xγ > LM(S(g1, g2)) = LM(u1gi1) > LM(u2gi2) > . . . > LM(utgit).

Quindi

xα(1)g1 − xα(2)g2 =

t∑

j=1

xδ−γujgij

e LM(xδ−γujgij ) < xδ = m. Quindi, poiche

f = c1(xα(1)g1 − xα(2)g2) + (c1 + c2)x

α(2)g2 + . . .+ csxα(s)gs


sostituendo si vede che otteniamo un’espressione della forma f = h1g1 + . . . + hsgs con vdiminuito oppure, nel caso in cui v = 2 e c1 + c2 = 0, con m diminuito. Ma questo non epossibile, quindi v = 1.

Segue che m = LM(xα(1)g1) = LM(f) e quindi LM(g1) divide LM(f). �

Algoritmo 1.1.31 Dati: {g1, . . . , gs} che genera un ideale I ⊂ k[x1, . . . , xn] e un fissatoordine monomiale ≤.

Calcoliamo: una base di Grobner per I rispetto a ≤.

1. Poniamo G0 = {g1, . . . , gs}, e i = 0.

2. Se S(f, g)G

per ogni f, g ∈ Gi allora Gi e una base di Grobner di I, e ci fermiamo.

3. Se esistono f, g ∈ Gi con r = S(f, g)G 6= 0 allora poniamo Gi+1 = Gi ∪ {r}, i := i+ 1,

e torniamo al passo 2.

Proposizione 1.1.32 L’algoritmo 1.1.31 termina correttamente.

Dimostrazione.

Quando l’algoritmo termina Gi e una base di Grobner per I perche:

- genera I in quanto contiene g1, . . . , gs e Gi ⊂ I.

- Per il Teorema 1.1.30 Gi e una base di Grobner.

L’algoritmo termina sempre. Infatti consideriamo gli ideali Ji = 〈LM(g) | g ∈ Gi〉. Di-ciamo che se Gi+1 ) Gi allora Ji+1 ) Ji. Infatti, Gi+1 = Gi ∪ {r} e LM(r) non e divisibileper ogni LM(g) per g ∈ Gi quindi LM(r) 6∈ Ji (Lemma 1.1.16). Ma LM(r) ∈ Ji+1 quindiJi+1 ) Ji.

Abbiamo anche visto che non esistono catene infinite strettamente crescenti di ideali ink[x1, . . . , xn] (Corollario 1.1.22). Quindi l’algoritmo deve terminare. �

Esempio 1.1.33 Siano g1 = xyz − xy e g2 = x2y − yz. Prendiamo l’ordine <glex conx >glex y >glex z.

Avremo G0 = {g1, g2} e

S(g1, g2) = xg1 − zg2

= x2yz − x2y − (x2yz − yz2)

= −x2y + yz2

g2→ yz2 − yz

= g3.

Quindi G1 = {g1, g2, g3}. Avremo

S(g1, g3) = zg1 − xg3

= xyz2 − xyz − (xyz2 − xyz)

= 0

12 Basi di Grobner

e

S(g2, g3) = z2g2 − x2g3

= x2yz2 − yz3 − (x2yz2 − x2yz)

= x2yz − yz3

g1→ −yz3 + x2yg3→ x2y − yz2

g2→ −yz2 + yzg3→ 0.

Quindi G1 = {g1, g2, g3} e una base di Grobner di I.

Per calcolare una base di Grobner ci sono alcuni trucchi che si possono usare. Innanzituttosi puo dividere ogni elemento di G con uno scalare per farlo monico. Cosı si calcolano piufacilmente. Un secondo trucco si basa sui seguenti risultati.

Lemma 1.1.34 Siano f, g ∈ k[x1, . . . , xn] e assumiamo che il minimo comune multiplo diLM(f) e LM(g) sia il prodotto LM(f)LM(g) (quindi il massimo comune divisore di LM(f)e LM(g) sia 1). Siano u, v polinomi in k[x1, . . . , xn] con LM(u) < LM(f), LM(v) < LM(g).Allora ug + vf riduce a 0 modulo {f, g}.Dimostrazione. Il monomio di testa di ug + vf appare in ug oppure in vf ma non inentrambi. Infatti se LM(ug) = LM(vf) allora LM(u)LM(g) = LM(v)LM(f) quindi, visto cheLM(g) e LM(f) non hanno fattori in comune segue che LM(g) divide LM(v). Ma LM(v) <LM(g) quindi non e possibile.

Segue che LM(ug) 6= LM(vf) e quindi il maggiore di questi sara LM(ug + vf).Supponiamo sia LM(ug + vf) = LM(ug). Segue che LM(ug + vf) e divisibile per LM(g)

con fattore LM(u). Quindi nell’algoritmo di divisione con resto ug + vf e rimpiazzato da

ug + vf − cLM(u)g = (u− cLM(u))g + vf

dove c ∈ k.In questo modo otteniamo un’espressione della stessa forma quindi si puo andare avanti

finche si ottiene zero. �

Lemma 1.1.35 Siano f, g ∈ k[x1, . . . , xn] tali che LM(f) e LM(g) non abbiano fattori incomune. Allora S(f, g) riduce a 0 modulo {f, g}.Dimostrazione. Scriviamo f = c1x

α + r1 e g = c2xβ + r2, con xα = LM(f) e xβ = LM(g).

Allora il minimo comune multiplo di xα e xβ e xα+β. Segue che

S(f, g) =xα+β

c1xα(c1x

α + r1) −xα+β

c2xβ(c2x

β + r2)

=1

c1r1x

β − 1

c2r2x

α

=1

c1c2r1(g − r2) −

1

c1c2r2(f − r1)

=1

c1c2(r1g − r2f)


e LM(r1) < LM(f), LM(r2) < LM(g). Per il Lemma 1.1.34, r1g − r2f riduce a zero modulo{f, g}. �

Conclusione. Nel calcolo di una base di Grobner non bisogna controllare S(f, g) se LM(f)e LM(g) hanno fattori in comune.

Esempio 1.1.36 Un problema con le basi di Grobner e che a volte sono molto difficili acalcolare, perche possono essere molto grandi. Consideriamo

f1 = x3 + y + z2 − 1, f2 = x2 + y3 + z − 1, f3 = x+ y2 + z3 − 1.

Una base di Grobner rispetto a <lex e

x + y + 7467678205870943/65719095621171465*z^25 +

1906548593713883/4381273041411431*z^24 +

8191728039103700/13143819124234293*z^23 -

18118488190106417/65719095621171465*z^22 -

40197573291173158/13143819124234293*z^21 -

60670103256071060/13143819124234293*z^20 -

152406006738162748/65719095621171465*z^19 +

80624458839890252/13143819124234293*z^18 +

649226374687018607/65719095621171465*z^17 +

618150565337585002/65719095621171465*z^16 +

353034549878420633/65719095621171465*z^15 +

238802559571273606/65719095621171465*z^14 -

11655150926515255/4381273041411431*z^13 -

1972928184800696599/65719095621171465*z^12 -

775940019593808291/21906365207057155*z^11 -

1345970642704934506/65719095621171465*z^10 +

2087861421527788238/65719095621171465*z^9 +

3117371817891097726/65719095621171465*z^8 +

374132655781594758/21906365207057155*z^7 -

437890362723893518/65719095621171465*z^6 -

60670429063906802/1991487746096105*z^5 -

42413702095534382/65719095621171465*z^4 -

28132496530919371/21906365207057155*z^3 +

702615426148730872/65719095621171465*z^2 -

80217895633896968/21906365207057155*z - 1,

y^2 - y - 7467678205870943/65719095621171465*z^25 -

1906548593713883/4381273041411431*z^24 -

8191728039103700/13143819124234293*z^23 +

18118488190106417/65719095621171465*z^22 +

40197573291173158/13143819124234293*z^21 +

60670103256071060/13143819124234293*z^20 +

152406006738162748/65719095621171465*z^19 -

80624458839890252/13143819124234293*z^18 -

649226374687018607/65719095621171465*z^17 -

14 Basi di Grobner

618150565337585002/65719095621171465*z^16 -

353034549878420633/65719095621171465*z^15 -

238802559571273606/65719095621171465*z^14 +

11655150926515255/4381273041411431*z^13 +

1972928184800696599/65719095621171465*z^12 +

775940019593808291/21906365207057155*z^11 +

1345970642704934506/65719095621171465*z^10 -

2087861421527788238/65719095621171465*z^9 -

3117371817891097726/65719095621171465*z^8 -

374132655781594758/21906365207057155*z^7 +

437890362723893518/65719095621171465*z^6 +

60670429063906802/1991487746096105*z^5 +

42413702095534382/65719095621171465*z^4 +

50038861737976526/21906365207057155*z^3 -

702615426148730872/65719095621171465*z^2 +

80217895633896968/21906365207057155*z,

y*z + 114351761873236539/148963283407988654*z^25 +

209291487801391117/446889850223965962*z^24 +

52236360062652115/148963283407988654*z^23 -

1468425502479577274/223444925111982981*z^22 -

858875628508250933/223444925111982981*z^21 -

616034236519743323/223444925111982981*z^20 +

8794492882346418295/446889850223965962*z^19 +

4815691490104347169/446889850223965962*z^18 +

1149199885582915487/446889850223965962*z^17 -

1088785538668067356/223444925111982981*z^16 -

2515633540839994712/223444925111982981*z^15 +

6870511665918010699/446889850223965962*z^14 -

33317003410103522629/446889850223965962*z^13 -

1138745048309366852/74481641703994327*z^12 -

2405659933320304387/223444925111982981*z^11 +

16532107971394002975/148963283407988654*z^10 +

38492638078382481727/446889850223965962*z^9 -

17305956248039834578/223444925111982981*z^8 -

3042243532386622694/223444925111982981*z^7 -

8470564338716612201/74481641703994327*z^6 +

109793303496803963/1194892647657663*z^5 -

1834169915554595837/74481641703994327*z^4 +

23672654350351476275/446889850223965962*z^3 -

2965819909779524184/74481641703994327*z^2 +

3212763377507509769/446889850223965962*z,

z^26 - 9*z^23 + 29*z^20 - 6*z^18 - 11*z^17 - 14*z^16 + 27*z^15 - 110*z^14 +

37*z^13 + 4*z^12 + 163*z^11 + 36*z^10 - 173*z^9 + 28*z^8 - 146*z^7 +

208*z^6 - 94*z^5 + 89*z^4 - 91*z^3 + 37*z^2 - 5*z

1.2 Applicazioni di basi di Grobner 15

1.2 Applicazioni di basi di Grobner

In questo secondo sezione vediamo alcune applicazioni di basi di Grobner. Innanzitutto pos-siamo risolvere il nostro problema iniziale: dato l’ideale I ⊂ k[x1, . . . , xn] e f ∈ k[x1, . . . , xn]decidere se f ∈ I. Per risolvere questo problema calcoliamo una base di Grobner G di I.Allora f ∈ I se e solo se fG = 0.

1.2.1 Risolvere equazioni polinomiali

Definizione 1.2.1 Un campo k e detto algebricamente chiuso se ogni polinomio in k[x] hauno zero in k.

Esempio 1.2.2 Un esempio e k = C.

Il problema e, dati i polinomi f1, . . . , fs in k[x1, . . . , kn], decidere se esiste un vettore(a1, . . . , an) ∈ kn con

f1(a1, . . . , an) = . . . = fs(a1, . . . , an) = 0

e trovare tali (a1, . . . , an).

Nel caso dove il campo e algebricamente chiuso la prima parte del problema viene risoltocon il Nullstellensatz di Hilbert.

Teorema 1.2.3 (Hilbert’s Nullstellensatz) Sia k un campo algebricamente chiuso e scri-viamo R = k[x1, . . . , xn]. Siano f1, . . . , fs ∈ R. Allora esiste un vettore a = (a1, . . . , an) ∈ kn

con f1(a) = . . . = fs(a) = 0 se e solo se l’ideale I ⊂ R generato da f1, . . . , fs non contiene 1.

Nella prova usiamo un lemma che non proviamo.

Lemma 1.2.4 Siano k ⊂ K campi tali che esistano ζ1, . . . , ζs ∈ K con la proprieta che ognielemento di K puo essere scritto come polinomio in ζ1, . . . , ζs con coefficienti in k. Allora Ke algebrico su k.

L’idea della prova e che se esiste un trascendente z ∈ K, allora k[z] e isomorfo ad unanello polinomiale, e k(z) e isomorfo al campo delle funzioni razionali in un variabile, su k.E quel campo non e finitamente generato su k.

Dimostrazione.(della Nullstellensatz). “⇒” Ovvio. Infatti se esiste a allora f(a) = 0 perogni f ∈ I quindi 1 6∈ I.

“⇐” Ogni catena di ideali I = I0 ⊆ I1 ⊆ I2 ⊆ . . . infinita ha la proprieta che esiste r conIr = Ir+1 = Ir+2 = . . . (Corollario 1.1.22). Quindi esiste un ideale massimale di R, J ⊃ I,J 6= R (N.B. se 1 ∈ I allora I = R). Allora K = k[x1, . . . , xn]/J e un campo.

Scriviamo ζi = xi mod J quindi ogni elemento di K e polinomio di ζi con coefficienti ink. Quindi K e algebrico du k (Lemma 1.2.4). Poiche k e algebricamente chiuso segue cheK = k.

Quindi xi mod J = ai per opportuni ai ∈ k e quindi xi−ai ∈ J . Ma l’ideale 〈x1 − a1, . . . , xn − an〉e massimale quindi J = 〈x1 − a1, . . . , xn − an〉.

Segue che per ogni f ∈ J si ha f(a1, . . . , an) = 0 e in particolare ogni f ∈ I. �

Usando il Nullstellensatz possiamo decidere se date equazioni polinomiali hanno o menouna soluzione dentro un campo algebricamente chiuso che contiene il campo base. Infatti:

16 Basi di Grobner

calcoliamo una base di Grobner G dell’ideale generato dai polinomi; allora una soluzioneeseiste se e solo se 1G 6= 0.

Adesso torniamo al problema di trovare le soluzioni di un insieme di equazioni polinomiali.Il seguente lemma e banale, ma di importanza fondamentale.

Lemma 1.2.5 Sia I l’ideale generato da f1, . . . , fs ∈ k[x1, . . . , xn], e sia a = (a1, . . . , an) ∈kn. Allora si ha che f1(a) = . . . = fs(a) = 0 se e solo se f(a) = 0 per ogni f ∈ I.

Dimostrazione. “⇒” Ovvio.

“⇐” Se f ∈ I allora esistono f1, . . . , fs ∈ k[x1, . . . , xn] con f =∑hifi quindi f(a) =∑

hi(a)fi(a) = 0. �

Da questo lemma vediamo che per risolvere le equazioni f1 = . . . = fs = 0 possiamoprendere qualsiasi insieme di polinomi che generano lo stesso ideale. In particolare possia-mo prendere una base di Grobner. Adesso vediamo che basi di Grobner rispetto all’ordinelessicografico sono particolarmente utili.

Definizione 1.2.6 Sia I ⊂ k[x1, . . . , xn] un ideale e 0 ≤ l ≤ n−1. Allora I∩k[xl+1, . . . , xn],ideale di k[xl+1, . . . , xn], e detto l-esimo ideale di eliminazione di I.

Si chiama cosı perche elimina le prime l variabili.

Teorema 1.2.7 (Teorema di eliminazione) Sia R = k[x1, . . . , xn] e si consideri l’ordine<lex con x1 >lex x2 >lex . . . >lex xn. Sia I ⊂ R un ideale e G una base di Grobner di Irispetto a <lex. Allora G ∩ k[xl+1, . . . , xn] e una base di Grobner per I ∩ k[xl+1, . . . , xn].

Dimostrazione. Poniamo Gl = G ∩ k[xl+1, . . . , xn] e Il = I ∩ k[xl+1, . . . , xn].

Bisogna provare che 〈LM(Il)〉 = 〈LM(g) | g ∈ Gl〉.“⊃” Ovvio perche Gl ⊂ Il.

“⊂” Sia f ∈ Il. Quindi f ∈ I e poiche G e una base di Grobner di I allora esiste g ∈ Gtale che LM(g) divide LM(f). Ma f ∈ k[xl+1, . . . , xn] quindi anche LM(g) ∈ k[xl+1, . . . , xn].

Sia xα un monomio di g, xα 6= LM(g). Se αi > 0 per i ≤ l allora xα >lex LM(g). Maquesta e una contraddizione.

Quindi xα ∈ k[xl+1, . . . , xn] e quindi g ∈ k[xl+1, . . . , xn]. Segue che g ∈ Gl e quindiLM(f) ∈ 〈LM(g) | g ∈ Gl〉. �

Conclusione. Con una base di Grobner rispetto a <lex troviamo basi di Grobner per

I ∩ k[xn]

I ∩ k[xn−1, xn]

...

I ∩ k[x2, . . . , xn]

I ∩ k[x1, . . . , xn] = I.

Quindi la base di Grobner ha una struttura triangolare che ci puo aiutare a risolvere il sistemadi equazioni polinomiali.

N.B. E’ possibile che I ∩ k[xl+1, . . . , xn] = 0.


Esempio 1.2.8 Consideriamo i polinomi

f1 = x2 + y + z − 1, f2 = x+ y2 + z − 1, f3 = x+ y + z2 − 1.

Vogliamo risolvere il sistema f1 = f2 = f3 = 0.

Una base di Grobner rispetto a >lex e costituita dai polinomi

g1 = x+ y + z2 − 1

g2 = y2 − y − z2 + z

g3 = 2yz2 + z4 − z2

g4 = z6 − 4z4 + 4z3 − z2 = z2(z − 1)2(z2 + 2z − 1).

Posto I = 〈f1, f2, f3〉 si vede che I ∩ k[z] e generato da g4, I ∩ k[y, z] e generato da g2, g3, g4.

Vediamo che g4 = 0 da un numero finito di valori per z, cioe 0, 1 e −1 ±√

2. Se z = 0allora anche g3 = 0, ma l’equazione g2 = 0 implica che y puo essere 0 o 1. Se y = z = 0, allorada g1 = 0 segue che x = 1. Troviamo la soluzione (1, 0, 0). Andando avanti cosı troviamo lesoluzioni

(1, 0, 0)

(0, 1, 0)

(0, 0, 1)

(−1 −√

2,−1 −√

2,−1 −√

2)

(−1 +√

2,−1 +√

2,−1 +√

2).

1.2.2 Applicazioni di basi di Grobner in geometria

Definizione 1.2.9 Sia I ⊂ k[x1, . . . , xn] un ideale. Allora

√I = {f ∈ k[x1, . . . , xn] | esiste m > 0 con fm ∈ I}

e chiamato radicale di I.

Osservazione 1.2.10 Si ha che√I e un ideale di k[x1, . . . , xn].

Dimostrazione. Ovviamente 0 ∈√I. Sia f ∈

√I e g ∈ k[x1, . . . , xn], quindi fm ∈ I. Allora

gmfm = (gf)m ∈ I e quindi gf ∈√I.

Se f, g ∈√I allora sia m > 0 con fm, gm ∈ I. Allora

(f + g)2m =

2m∑

i=0

(2m

i

)f ig2m−i ∈ I

e quindi f + g ∈√I. �

Lemma 1.2.11 Sia I = 〈f1, . . . , fs〉 ⊂ k[x1, . . . , xn] un ideale e f ∈ k[x1, . . . , xn]. Alloraf ∈

√I se e solo se 1 e contenuto nell’ideale J = 〈f1, . . . , fs, 1 − yf〉 ⊂ k[x1, . . . , xn, y].

18 Basi di Grobner

Dimostrazione. “⇒” Supponiamo che fm ∈ I. Allora ymfm ∈ J (perche I ⊂ J). Maanche

(1 − ymfm) = (1 − yf)(1 + yf + (yf)2 + . . .+ (yf)m−1) ∈ J

quindi 1 ∈ J .

“⇐” Se 1 ∈ J allora esistono pi, q ∈ k[x1, . . . , xn, y] con

1 =

s∑

i=1

pi(x1, . . . , xn, y)fi + q(x1, . . . , xn, y)(1 − yf).

Sostituendo y con 1f otteniamo

1 =

s∑

i=1

pi(x1, . . . , xn,1

f)fi.

Ora osserviamo che i pi(x1, . . . , xn,1f ) sono espressioni razionali con denominatori f r per

certi r ≥ 0.

Segue che esiste m con fmpi(x1, . . . , xn,1f ) ∈ k[x1, . . . , xn] e quindi

fm =

s∑

i=1

fmpi(x1, . . . , xn,1

f)fi

e quindi fm ∈ I, vale a dire f ∈√I. �

Quindi usando basi di Grobner possiamo verificare se f ∈√I con il seguente algoritmo.

Algoritmo 1.2.12 Dati: f1, . . . , fs che generano l’ideale I ⊂ k[x1, . . . , xn], e un f ∈ k[x1, . . . , xn].Decidiamo se f ∈

√I o meno.

1. Calcoliamo una base di Grobner di J = 〈f1, . . . , fs, 1 − yf〉;

2. Se 1 ∈ J allora f appartiene a√I altrimenti non gli appartiene.

Definizione 1.2.13 Sia W = kn uno spazio vettoriale su k di dimensione n e sia I =〈f1, . . . , fs〉 un ideale di k[x1, . . . , xn]. Allora l’insieme

V (I) = {(w1, . . . , wn) ∈W | f(w1, . . . , wn) = 0 per ogni f ∈ I}

e chiamato insieme chiuso corrispondente a I.

Esempio 1.2.14 Sia I ⊂ k[x, y] generato da y − x2 e k = R. Allora V (I) e costituito datutti i punti del seguente grafico.


V

Analogamente sia I generato da x2 + y2 − 1. Allora V (I) e costituito da tutti i punti delseguente grafico.

V (I)

Teorema 1.2.15 (Hilbert’s Nullstellensatz, forma forte) Sia k un campo algebricamen-te chiuso e I ⊂ k[x1, . . . , xn] un ideale. Sia J ⊂ k[x1, . . . , xn] l’ideale

J = {f ∈ k[x1, . . . , xn] | f(w) = 0, ∀w ∈ V (I)}.

Allora J =√I.

Dimostrazione. Se f ∈√I allora esiste m > 0 con fm ∈ I quindi fm(w) = 0 per ogni

w ∈ V (I). Ma fm(w) = (f(w))m quindi f(w) = 0 per ogni w ∈ V (I). Allora f ∈ J .Prendiamo f ∈ J quindi f(w) = 0 per ogni w ∈ V (I). Sia I generato da f1, . . . , fs ∈

k[x1, . . . , xn]. Sia I = 〈f1, . . . , fs, 1 − yf〉 ⊂ k[x1, . . . , xn, y]. Sia w = (w1, . . . , wn, wn+1) ∈kn+1. Abbiamo due casi:

- (w1, . . . , wn) ∈ V (I). Allora fi(w) = 0 per i = 1, . . . , s. Ma f(w) = 0 quindi (1−yf)(w) 6= 0.

- (w1, . . . , wn) 6∈ V (I). Allora esiste fi con fi(w) 6= 0.

In conclusione {w = (w1, . . . , wn+1) | h(w) = 0, ∀h ∈ I} = ∅. Per la forma debole delHilbert’s Nullstellensatz (Teorema 1.2.3), 1 ∈ I (k e algebricamente chiuso). Quindi per ilLemma 1.2.11, f ∈

√I. �

20 Basi di Grobner

Osservazione 1.2.16 Si haV (I) ∩ V (J) = V (I + J)

dove I + J e l’idealeI + J = {f + g | f ∈ I, g ∈ J}.

Dimostrazione. Sia v ∈ V (I) ∩ V (J) e h = f + g ∈ I + J con f ∈ I e g ∈ J . Si ha

h(v) = f(v) + g(v) = 0 + 0 = 0

quindi v ∈ V (I + J).Viceversa, sia v ∈ V (I + J). Poiche I ⊂ I + J sia ha che h(v) = 0 per ogni h ∈ I quindi

v ∈ V (I). Analogamente si vede che v ∈ V (J) quindi v ∈ V (I) ∩ V (J). �

Segue che per X ⊂ kn esiste un unico insieme chiuso minimale che contiene X. Questo edetto chiusura di X. Si consideri

Id(X) = {f ∈ k[x1, . . . , xn] | f(v) = 0, ∀v ∈ X}

ideale di k[x1, . . . , xn]. Allora la chiusura di X e V (Id(X)).

Teorema 1.2.17 Sia k algebricamente chiuso, sia R = k[x1, . . . , xn] e I = 〈f1, . . . , fs〉 ⊂ R.Sia πl : k

n → kn−l con πl(v1, . . . , vn) = (vl+1, . . . , vn).Sia Il = k[xl+1, . . . , xn] ∩ I, l-esimo ideale di eliminazione. Allora V (Il) e la chiusura di

πl(V (I)).

Esempio 1.2.18 Sia I = 〈xy − 1〉 ⊂ k[x, y]. Consideriamo π1 : k2 → k con π1(v1, v2) = v2.Allora

V (I) = {(v1, v2) | v1v2 = 1} =⇒ π1(V (I)) = k r {0}.Ora abbiamo I1 = 0 che implica V (I1) = k.

Dimostrazione.(del Teorema 1.2.17) “⊃”. Sia v = (v1, . . . , vn) ∈ V (I). Allora f(v) =0 per ogni f ∈ I. In particolare per ogni f ∈ Il ⊂ k[xl+1, . . . , xn] abbiamo f(πl(v)) =f(vl+1, . . . , vn) = 0.

Quindi V (Il) e un insieme chiuso che contiene πl(V (I)) e quindi V (Il) contiene la chiusuradi πl(V (I)).

“⊂” Sia J = Id(πl(V (I)) ⊂ k[xl+1, . . . , xn]. Diciamo che J ⊂ √Il. Infatti f ∈ J implica

f(vl+1, . . . , vn) = 0 per ogni (v1, . . . , vn) ∈ V (I). Segue che f(v) = 0 per ogni v ∈ V (I) equindi, per Hilbert’s Nullstellensatz (Teorema 1.2.15), f ∈

√I e percio fm ∈ I.

Ma f ∈ k[xl+1, . . . , xn] quindi anche fm e quindi fm ∈ I ∩ k[xl+1, . . . , xn] = Il. Segue chef ∈ √

Il.Concludiamo V (J) ⊃ V (

√Il) = V (Il). �

Conclusione. Tramite basi di Grobner possiamo trovare la chiusura di πl(U) dove U e uninsieme chiuso.

Un’applicazione di questo e l’immagine di una funzione regolare.Una funzione regolare h : kn → km e data da m polinomi h1, . . . , hm ∈ k[x1, . . . , xn] e

h(v) = (h1(v), . . . , hm(v)).Sia X = V (I) ⊂ kn dove I = 〈f1, . . . , fs〉 ⊂ k[x1, . . . , xn]. Che cos’e la chiusura di h(X)?


SiaΓ = {(v, h(v)) | v ∈ X} ⊂ kn+m.

Questo viene detto grafico di h.Osserviamo che Γ ⊂ kn+m e chiuso. Infatti, sia J l’ideale di k[x1, . . . , xn, y1, . . . , ym]

generato da{f1, . . . , fs, y1 − h1, . . . , ym − hm}.

Allora (v,w) ∈ Γ se e solo se p(v,w) = 0 per ogni p ∈ J (w = h(v) se e solo se (yi−hi)(v,w) =wi − hi(v) = 0).

Con basi di Grobner Possiamo calcolare la chiusura di πn(Γ) dove πn : kn+m → km e

πn(v1, . . . , vn, w1, . . . , wm) = (w1, . . . , wm).

Ora πn(Γ) = h(X) quindi possiamo calcolare la chiusura di h(X) (assumiamo sempre chek sia algebricamente chiuso).

Esempio 1.2.19 Sia S = {(t2, t3) | t ∈ C}. Calcoliamo la chiusura di S. Definiamo h : C →C2 con h(t) = (t2, t3). Allora S = {h(t) | t ∈ C}. Consideriamo il grafico di h:

Γ = {(u, h(u)) | u ∈ C}.

Abbiamo che Γ = V (I) dove I = 〈y1 − t2, y2 − t3〉 ⊂ k[t, y1, y2].Calcoliamo una base di Grobner di I rispetto a <lex con t >lex y1 >lex y2, e otteniamo

G = {t2 − y1, ty1 − y2, ty2 − y21, y

31 − y2

2}.

Quindi per il Teorema di eliminazione, la base di Grobner di I ∩ k[y1, y2] e G ∩ k[y1, y2] ={y3

1 − y22}. La conclusione e che la chiusura di S e V (J) dove J e generato da y3

1 − y22.

In questo caso abbiamo V (I) = S, ma questo non vale in generale.L’insieme S e la forma parametrica di una curva in C2, mentre la rappresentazione tramite

equazioni polinomiali (cioe come V (J)) e chiamata la forma implicita della curva. Quindi none sempre vero che la forma parametrica e quella implicita danno esattamente lo stesso insiemedi punti.

1.2.3 Polly-cracker

Qui descriviamo brevemente un crittosistema che e basato sulla difficolta di calcolare basi diGrobner.

Alice vuole ricevere messaggi segreti da Bob. Alice sceglie un campo finto Fq (per esempioF2) e lavora dentro R = Fq[x1, . . . , xn]

Alice sceglie un y ∈ Fnq e alcuni polinomi f1, . . . , fs ∈ R con fi(y) = 0. La chiave pubblica

e f1, . . . , fs e la chiave segreta e y.Per mandare un messaggio Bob prima codifica il messaggio come un m ∈ Fq poi sceglie

polinomi h1, . . . , hs ∈ R e manda f = m+∑hifi ad Alice.

Alice puo leggere il messaggio perche f(y) = m+∑hifi(y) = m.

Con le basi di Grobner si puo rompere il sistema. SeG e una base di Grobner di 〈f1, . . . , fs〉allora il resto di f dopo la divisione modulo G sara m.

Bisogna scegliere i polinomi fi tali che una base di Grobner dell’ideale 〈f1, . . . , fs〉 siadifficile da calcolare.

22 Basi di Grobner

Una strategia per scegliere gli f1, . . . , fs e la seguente: si prende un problema che e provatoessere difficile da risolvere, un cosiddetto NP-completo, e si riformula questo problema intermini di equazioni polinomiali e si spera che in questo caso la base di Grobner sia difficileda calcolare.

Consideriamo per esempio la 3-colorazione di un grafo Γ = (V,E) (V=vertice, E=lato).Una 3-colorazione e una funzione ϕ : V → {1, 2, 3} con la proprieta che se v,w ∈ V sonocollegati da una lato allora ϕ(v) 6= ϕ(w). Esempio:

1

2 3

2

3

1

Si sa che in generale il problema di trovare una 3-colorazione di un grafo qualsiasi e moltodifficile (e un problema NP-completo).

Adesso prendiamo F2 come campo base, e prendiamo i variabili tv,i per v ∈ V e i ∈{1, 2, 3}. Sia B = B1 ∪B2 ∪B3 dove

B1 = {tv,1 + tv,2 + tv,3 − 1 | v ∈ V }B2 = {tv,itv,j | v ∈ V, 1 ≤ i < j ≤ 3}B3 = {tu,itv,i | uv ∈ E, 1 ≤ i ≤ 3}.

Poniamo tv,i = 1 se il vertice v ha colore i, e tv,i = 0 altrimenti. Questo definisce unpunto dove tutti gli elementi di B si annullano. Vice versa: se abbiamo un punto dovetutti gli elementi di B si annullano possiamo dedurre una 3-colorazione del grafo. Infatt,dall’annullamento degli elementi di B1 ∪ B2 troviamo il colore di ogni vertice, mentre chel’annullamento degli elementi di B3 esprime che due vertici connessi non possono avere lostesso colore.

Esperimenti dimostrano che e difficile rompere il Polly Cracker corrispondente ad ungrafo abbastanza grande mediante basi di Grobner. Pero, ci sono altri metodi per cercarledi romperlo, che rendono il sistema insicuro. Per esempio, si puo osservare che, se f =m+

∑i hifi e un messaggio, allora

m = f(0) −∑

i

hi(0)fi(0).

Quindi basta conoscere i termini costanti degli hi per ricavare il messaggio. A volte, queitermini costanti si possono ottenere studiando come e possibile ottenere il polinomio f comecombinazione dei polinomi fi.

1.3 Esercizi

1. Consideriamo l’ordine <rlex definito con xα <rlex xβ se αk < βk dove k e massimale tale

che αk 6= βk. Provare che <rlex e un ordine monomiale.

1.3 Esercizi 23

2. Sia < un ordine monomiale e 1 ≤ i ≤ n. Definiamo <i con xα <i xβ se α1 + · · · + αi <

β1 + · · · + βi o α1 + · · · + αi = β1 + · · · + βi e xα < xβ. Provare che <i e un ordinemonomiale.

3. Si usa l’ordine <glex (lessicografico graduato). Siano f1 = y2−z, f2 = z3−y, f2 = z2−1,e g = xy2z2 + xy − yz. Trovare tutti is resti possibili di g modulo f1, f2, f3.

4. Sia A ⊂ Zn≥0 un insieme finito, e I = 〈xα | α ∈ A〉 l’ideale monomiale corrispondente.

Dimostrare che f ∈ I se e solo se il resto ottenuto mediante la divisione con resto di fmodulo {xα | α ∈ A} e 0.

5. Sia I ⊂ k[x1, . . . , xn] l’ideale generato da f1, . . . , fr, e supponiamo che

〈LM(f1), . . . ,LM(fr)〉 6= 〈LM(I)〉.

Dimostrare che esiste f ∈ I tale che la divisione con resto di f modulo f1, . . . , fr nonda il resto 0.

6. Calcolare S(f, g) per f = 4x2z − 7y2, g = xyz2 + 3xz4, e f = x4y − z2, g = 3xz2 − y,rispetto al ordine <lex.

7. Siano g1 = x − z2, g2 = y − z3 ∈ k[x, y, z]. Provare che G = {g1, g2} e una base diGrobner rispetto al ordine <lex. Provare che non e una base di Grobner rispetto alordine <glex. Calcolare una base di Grobner dell’ideale generato da G rispetto a <glex.

8. Siano g1 = x2y − 1, g2 = xy2 − x. Calcolare una base di Grobner dell’ideale I ⊂ k[x, y]generato da g1, g2, rispetto a <glex.

9. Sia I ⊂ k[x, y, z] l’ideale generato da g1 = x2yz − yz − x, g2 = xy2z − xy − y, g3 =xyz2 −xy− z. Usiamo l’ordine <glex. Calcolare una base di Grobner direttamente e unpo’ laborioso. Invece si puo fare cosı:

(a) Calcolare g4 = S(g1, g2) (ridotto modulo g1, g2, g3), e g5 = S(g1, g3) (ridottomodulo g1, . . . , g4).

(b) Calcolare S(g2, g5), ridotto modulo g1, . . . , g5.

(c) Provare che I e anche generato da h1 = x2z2−z2−x, h2 = xz3−xz−z, h3 = y−z.(d) Calcolare h4 = S(h1, h2), h5 = S(h1, h4), h6 = S(h2, h5).

(e) Provare che I e anche generato da h2, h3, h5, h6. Provare che formano una base diGrobner per I.

(f) Trovare u1, u2, u3 ∈ k[x, y, z] con y − z = u1g1 + u2g2 + u3g3

10. Siano g1 = x2 + 2y2 − 3, g2 = xy− y2 + 3 elementi di C[x, y]. Sia I l’ideale generato dag1, g2.

(a) Trovare una base di Grobner di I rispetto a <lex.

(b) Trovare una base di Grobner per I ∩ C[y].

(c) Trovare le soluzioni delle equazioni g1 = g2 = 0.

11. Siano g1 = x2 + y2 + z2 − 4, g2 = x2 + 2y2 − 5, g3 = xz − 1 elementi di C[x, y, z]. Sia Il’ideale generato da g1, g2, g3.

24 Basi di Grobner

(a) Usiamo l’ordine monomiale<lex. Calcolare g4 = S(g1, g2) (ridotto modulo g1, g2, g3),e g5 = S(g1, g3) (ridotto modulo g1, . . . , g4), e g6 = S(g3, g5) (ridotto modulog1, . . . , g5).

(b) Provare che g4, g5, g6 generano I, e che formano una base di Grobner per I.

(c) Calcolare basi di Grobner per I ∩ C[y, z] e I ∩ C[z].

(d) Calcolare tutte le soluzioni di g1 = g2 = g3 = 0.

12. Sia I ⊂ C[x, y, z] l’ideale generato da g1 = x2yz − yz − x, g2 = xy2z − xy − y, g3 =xyz2 − xy − z. Siano f1 = x− z4 + z2, f2 = y − z, f3 = z7 − 2z5 + z3 − z.

(a) Provare che I = 〈f1, f2, f3〉 (suggerimento: si puo usare il risultato del esercizio 9).

(b) Provare che {f1, f2, f3} e una base di Grobner di I rispetto all’ordine <lex (conx >lex y >lex z).

(c) Provare che f3 e libero di quadrati (suggerimento: su puo calcolare il massimocomune divisore di f3 e f ′3).

(d) Quanti punti a = (a1, a2, a3) ∈ C3 ci sono con f1(a) = f2(a) = f3(a) = 0?

13. Sia I = 〈x2, y2〉 ⊂ k[x, y]. Provare che x+ y ∈√I, calcolando una base di Grobner.

14. (Parametrizzazione razionale.) Sia

C = {(

2t

t2 + 1,1 − t2

t2 + 1

)| t ∈ C, t2 6= −1}.

Siano f1 = (t2 + 1)y1 − 2t, f2 = (t2 + 1)y2 − 1 + t2 ∈ C[t, y1, y2]. Poniamo

Γ = {(s, u1, u2) ∈ C3 | f1(s, u1, u2) = f2(s, u1, u2) = 0}.

(a) Sia π1 : C3 → C2 definito da π1(s, u1, u2) = (u1, u2). Provare che π1(Γ) = C.

(b) Usiamo l’ordine <lex, dove t >lex y1 >lex y2. Calcolare S(f1, f2) (ridotto modulof1, f2) e ottenere f3. Nello stesso modo calcolare S(f2, f3) e ottenere f4 e S(f3, f4)per ottenere f5.

(c) Provare che {f3, f4, f5} e una base di Grobner per l’ideale generato da f1, f2,rispetto a <lex.

(d) Trovare un ideale J ⊂ C[y1, y2] tale che V (J) e la chiusura di C.

15. SiaS = {(uv, uv2, u2) ∈ C3 | u, v ∈ C}.

Una base di Grobner di 〈uv − x, uv2 − y, u2 − z〉, rispetto all’ordine <lex con u >lex

v >lex x >lex y >lex z e

{u2 − z, uv − x, ux− vz, uy − x2, v2z − x2, vx− y, vyz − x3, x4 − y2z}.

Trovare un ideale I ⊂ C[x, y, z] tale che la chiusura di S e V (I). Trovare punti su V (I)che non ci sono su S. (Quindi V (I) e strettamente piu grande di S.)

Capitolo 2

Fattorizzazione di numeri interi infattori primi

Ci sono tre tipi di algoritmi che hanno da fare con il problema di fattorizzare un numero infattori primi:

1) test di primalita (probabilistico): un test di questo tipo prova che n non e primo oppuredice che n e probabilmente primo (tipicamente questi metodi sono veloci);

2) algoritmi per provare che un dato n che e probabilmente primo (come stabilito da un testdi primalita) e primo;

3) algoritmi per fattorizzare n quando si sa che n non e primo.

2.1 Fattorizzazione

Qui abbiamo dato un intero n di cui sappiamo che non e primo, e vogliamo trovare i suoifattori primi.

Il primo algoritmo per questo e di dividere n per ogni interno ≤ √n. Questo algoritmo

non funziona per interi grandi. Pero, i programmi per fattorizzare usano un elenco dei primiN numeri primi (circa N = 104 o N = 105 per esempio) per trovare fattori piccoli.

2.1.1 Metodo di Fermat

Assumiamo n dispari. Poniamo

A = {(a, b) | 0 < a ≤ b e n = ab}

eB = {(s, t) | 0 ≤ s < t e n = t2 − s2}.

Esiste una funzione biiettiva σ : A→ B con σ(a, b) =(

b−a2 , b+a

2

).

Funziona perche (b+ a

2

)2

−(b− a

2

)2

= ab = n

eσ−1(s, t) = (t− s, t+ s).

26 Fattorizzazione di numeri interi in fattori primi

Concludiamo che trovare una fattorizzazione n = ab e equivalente a trovare s e t conn = t2 − s2. Quindi abbiamo il seguente algoritmo.

Algoritmo 2.1.1 Dato: n che non e primo.Calcoliamo: a, b > 1 con n = ab.

1. Poniamo t0 = ⌈√n⌉ = min{k ∈ Z | k ≥ √n}.

2. Se t2i − n = s2i e un quadrato, allora mettiamo a = (ti + si), e b = (ti − si). Altrimentiponiamo ti+1 = ti + 1, e continuiamo.

Questo algoritmo termina correttamente perche se n = t2 − s2 con s < t allora t2 = n+ s2

implica t >√n.

Esempio 2.1.2 Sia n = 39. Si ha

t0 = 7 ⇒ 72 − 39 = 10t1 = 8 ⇒ 82 − 39 = 25 = 52

quindi (8 + 5)(8 − 5) = 39.

Questo algoritmo funziona bene se s e piccolo perche allora t e vicino a√n quindi bastano

pochi passi, anche se i fattori sono grandi.

2.1.2 Basi di fattori

Alcuni metodi piu avanzati si basano sull’algoritmo di Fermat. Ma invece di cercare s e t conn = t2 − s2, si cercano x e y con

- x2 − y2 = 0 mod n;

- 0 < y < x < n;

- x+ y 6= n.

Se abbiamo tali x e y abbiamo fattorizzato n perche (x+ y)(x− y) e divisibile per n. Max + y non e divisibile per n (perche x + y 6= n e x + y < 2n) e x − y non e divisibile per n.Quindi a = mcd(x+y, n) e b = mcd(x−y, n) sono fattori non banali (cioe a, b 6= 1 e a, b 6= n).

Esempio 2.1.3 Sia n = 377. Allora

3352 = 256 mod 377 = 162 mod 377

quindi prendiamo x = 335 e y = 16 e abbiamo

mcd(335 + 16, n) = 13 e mcd(335 − 16, n) = 29

quindi n = 13 · 29.

2.1 Fattorizzazione 27

Quindi l’idea e di trovare x con 0 < x < n tale che x2 mod n sia un quadrato y2. Nontutti gli x vanno bene. Per esempio, se n = 15 e prendiamo x = 2 abbiamo x2 mod n = 4 may = 2 non funziona perche y = x. Anche x = 13 non va bene perche x2 mod n = 4 ma cony = 2 si ha x+ y = n. Proviamo con x = 7 e troviamo 72 mod n = 4 e

mcd(7 + 2, 15) = 3 e mcd(7 − 2, 15) = 5

quindi x = 7 va bene.Notazione. x mod n sara l’unico intero s con −n

2 < s ≤ n2 , congruente a x mod n.

Definizione 2.1.4 Un insieme B = {p0 = −1, p1, . . . , pr} con pi primo e chiamato base difattori.

Definizione 2.1.5 Un intero k e detto B-numero (o B-liscio) se k = pe0

0 pe1

1 · · · perr .

Per trovare x tale che x2 mod n sia un quadrato si puo:

- scegliere una base di fattori;

- generare molti interi bi tali che b2i mod n e un B-numero.

Poi si spera che per un prodotto bi1 · · · bim si abbia

(bi1 · · · bim)2 mod n = pe0

0 pe1

1 · · · perr

con ei pari per ogni i, e quindi pe1

1 · · · perr = y2.

Esempio 2.1.6 Come nell’Esempio 2.1.3 sia n = 377 e prendiamo B = {−1, 2}. Allora

192 = −16 mod n e − 16 = p0p21

972 = −16 mod n e − 16 = p0p21.

Ora abbiamo (19 · 97)2 = p20p

41 mod n. Allora poniamo x = 19 · 97 = 335 mod n, e y = 16.

Infatti, mcd(335 + 16, 377) = 13 e mcd(335 − 16, 377) = 29 sono fattori di n.

Un metodo famoso per generare bi si base sulle frazioni continue.

2.1.3 Frazioni continue

Una frazione continua e un’espressione della forma

a0 +1

a1 + 1a2+ 1

a3+ 1a4

con ai ∈ Z, a0 > 0 e ai ≥ 1 per i ≥ 1.Notazione. L’espressione di sopra si indica con [a0; a1, a2, a3, a4].Piu generalmente diciamo che una frazione continua e una seguenza [a0; a1, . . . , an], con

ai ∈ Z, a0 ≥ 0, ai ≥ 1 per i ≥ 1. Il numero razionale γ corrispondente e definito cosı: sen = 0 allora γ = a0. Se n > 0 sia γ′ il numero razionale corrispondente alla frazione continua[a1; a2, . . . , an]. Poi

γ = a0 +1

γ′.


Sia x > 0 in R. Vogliamo trovare a0, a1, . . . tali che le frazioni continue [a0; a1, . . . , ak]siano buone approssimazioni per x, che convergono a x se k → ∞ (non e ancoara chiaro chee sempre possibile trovare tali ai; lo mostreremo nel seguito).

Gli ai, se esistono, si trovano cosı: Scriviamo x = a0 + 1x1

con a0 = ⌊x⌋ = max{n ∈ Z |n ≤ x}.

Avremo x1 = 1x−a0

. Poi scriviamo x1 = a1 + 1x2

con a1 = ⌊x1⌋ e quindi x2 = 1x1−a1

e cosıvia.

Piu formalmente, poniamo x0 = x e per i ≥ 0:

ai = ⌊xi⌋,

xi+1 =1

xi − ai.

Esempio 2.1.7 Sia x =√

2. Allora avremo x0 = x e

a0 = 1 ⇒ x1 =1√

2 − 1= 1 +

√2

a1 = 2 ⇒ x2 =1√

2 − 1= 1 +

√2

a2 = 2 ⇒ x3 =1√

2 − 1= 1 +

√2

e andando avanti cosı otteniamo ai = 2 per ogni i ≥ 1. Qui troviamo per esempio

[1; 2, 2, 2, 2] = 1 +1

2 + 12+ 1

2+ 12

=41

29.

Abbiamo che 2 − (4129 )2 = 1

841 ; quindi e una buona approssimazione di√

2.

Lemma 2.1.8 Se x ∈ Q allora l’algoritmo per calcolare la frazione continua termina (cioe aun certo punto troviamo xi − ai = 0). La frazione continua e quindi uguale a x.

Dimostrazione. Se x = ab scriviamo a = q1b+ r1 con 0 ≤ r1 < b. Avremo quindi

a0 = q1 e x1 =1

ab − q1

=b

r1.

Adesso scriviamo b = q2r1 + r2 con 0 ≤ r2 < r1 quindi

a1 = q2 e x2 =r1r2

e cosı si va avanti.Allora l’algoritmo termina perche 0 ≤ ri+1 < ri, e quindi ad un certo punto si trova i con

ri = 0.Si prova con induzione sul numero di passi che prende l’algoritmo che la frazione continua

che viene fuori e uguale a x. �

Possiamo scrivere bi

ci= [a0; a1, . . . , ai] e mcd(bi, ci) = 1. Questi si chiamano convergenti

della frazione continua per x.


Esempio 2.1.9 Sia x =√

2. Avremo

1 +1

2 + 12

=7

5=b2c2.

Teorema 2.1.10 Siano a0, a1, . . ., gli interi che vengono fuori dall’algoritmo per trovare lafrazione continua che approssima x ∈ R, x > 0. Poniamo

β0 = a0, β1 = a0a1 + 1, βi = aiβi−1 + βi−2,γ0 = 1, γ1 = a1, γi = aiγi−1 + γi−2,

per i ≥ 2. Allora

1) βiγi−1 − βi−1γi = (−1)i−1, i ≥ 1;

2) mcd(βi, γi) = 1;

3) bi = βi e ci = γi dove bi, ci ∈ Z≥0 sono tali che mcd(bi, ci) = 1 e bi

ci= [a0; a1, . . . , ai]. .

Dimostrazione. 1) Procediamo per induzione. Per i = 1 abbiamo

β1γ0 − β0γ1 = (a0a1 + 1)1 − a0a1 = 1 = (−1)0.

Per i ≥ 1 si ha, sfruttando l’ipotesi induttiva

βi+1γi − βiγi+1 = (ai+1βi + βi−1)γi − βi(ai+1γi + γi−1)

= βi−1γi − βiγi−1

= −(−1)i−1

= (−1)i.

2) Se p divide γi e βi allora per la 1) divide anche (−1)i−1 ma questo non e possibile.3) Procediamo per induzione su i. Per i = 0 si ha

b0c0

= a0 =β0

γ0

e per i = 1b1c1

= a0 +1

a1=β1

γ1.

Osserviamo che [a0; a1, . . . , ai, ai+1] e ottenuto da [a0; a1, . . . , ai] sostituendo ai con ai +1

ai+1. Per induzione abbiamo che

[a0; a1, . . . , ai] =βi

γi=aiβi−1 + βi−2

aiγi−1 + γi−2

quindi

[a0; a1, . . . , ai+1] =

(ai + 1

ai+1

)βi−1 + βi−2

(ai + 1

ai+1

)γi−1 + γi−2

=ai+1(aiβi−1 + βi−2) + βi−1

ai+1(aiγi−1 + γi−2) + γi−1

=ai+1βi + βi−1

ai+1γi + γi−1

=βi+1

γi+1.


Segue che βi+1 = bi+1 e γi+1 = ci+1 (visto che mcd(βi+1, γi+1) = 1). �

Osservazione 2.1.11 Segue che bici−1−cibi−1 = (−1)i−1. Dividiamo per cici−1 e otteniamo

bici

− bi−1

ci−1=

(−1)i−1

cici−1

quindi ∣∣∣∣bici

− bi−1

ci−1

∣∣∣∣ =1

cici−1.

Ma ci > ci−1 > . . . ≥ 1 quindi∣∣∣∣bici

− bi−1

ci−1

∣∣∣∣ −→ 0.

Teorema 2.1.12 Le notazioni sono quelle di Teorema 2.1.10. Allora bi

ciconverge a x per

i→ ∞.

Dimostrazione. Per i ≥ 0 poniamo xi = xi − ai. Allora

x = a0 +1

a1 + 1a2+... 1

ai+xi

.

Infatti, per i = 0 abbiamo a0 + x0 = x0 = x. Per i > 0 usiamo induzione. Per l’ipotesiinduttiva abbiamo che

a1 +1

a2 + 1a3+... 1

ai+xi

= x1,

che implica la tesi.Conclusione: x e ottenuto da [a0; a1, . . . , ai+1] sostituendo ai+1 con 1

exi. Ma

[a0; a1, . . . , ai+1] =bi+1

ci+1=ai+1bi + bi−1

ai+1ci + ci−1

quindi

x =1exibi + bi−1

1exici + ci−1

=bi + xibi−1

ci + xici−1.

Osservazione 2.1.13 Se prendiamo un vettore che va in un punto (s, t), allora ts indica la

pendenza. Se prendo i vettori che vanno in (ci, bi) e (xici−1, xibi−1) e faccio la somma, ottengoil vettore (ci + xici−1, bi + xibi−1).

(ci, bi)

(xici−1, xibi−1)

(ci + xici−1, bi + xibi−1)


Quindi bi+ exibi−1

ci+ exici−1e tra bi

cie bi−1

ci−1(o viceversa).

Da Osservazione 2.1.11 abbiamo che la distanza tra bi

cie bi+1

ci+1va a 0. Quindi bi

ciconverge

a un limite che coincidera con x. �

2.1.4 Fattorizzazione con frazioni continue

Lemma 2.1.14 Sia x ∈ R, x > 1. Siano bi

cii convergenti della frazione continua per x.

Allora|b2i − c2i x

2| < 2x.

Dimostrazione. Osservazione 2.1.11 dice che∣∣∣∣bi+1

ci+1− bici

∣∣∣∣ =1

ci+1ci.

Poniamo δ = 1ci+1ci

.

bi+1

ci+1x bi

ci

δ

Adesso

|b2i − c2i x2| = |c2i x2 − b2i | = c2i

∣∣∣∣x− bici

∣∣∣∣∣∣∣∣x+

bici

∣∣∣∣ .

Ora∣∣∣x− bi

ci

∣∣∣ < δ mentre

∣∣∣∣x+bici

∣∣∣∣ = x+bici

= 2x+bici

− x < 2x+ δ

quindi|b2i − c2i x

2| < c2i δ(2x+ δ).

Quindi

|b2i − c2i x2| − 2x < 2x

(−1 + δc2i +

δ2c2i2x

)= 2x

(−1 +

cici+1

+1

2xc2i+1

).

Ma 12xc2i+1

< 1ci+1

perche x > 1 e ci+1 ≥ 1. Inoltre ci + 1 ≤ ci+1 perche ci < ci+1. Quindi

|b2i − c2i x2| − 2x < 2x

(−1 +

cici+1

+1

ci+1

)< 2x

(−1 +

ci+1

ci+1

)= 0

e dunque|b2i − c2i x

2| < 2x.

�


Corollario 2.1.15 Sia n > 8 un intero e bi

cii convergenti per la frazione continua per

√n.

Allora |b2i mod n| < 2√n dove b2i mod n e l’unico intero congruente a n nell’intervallo

(−n2 ,

n2 ].

Dimostrazione. Per il Lemma 2.1.14 si ha |b2i − c2in| < 2√n. Ma b2i − c2in e un intero

congruente a b2i mod n e sta nell’intervallo (−2√n, 2

√n). Quindi sta nell’intervallo

(−n

2 ,n2

)

(visto che n > 8). Segue che b2i − c2in e uguale a b2i mod n. �

Idea dell’algoritmo: Sia B = {p0 = −1, p1, . . . , pr} una base di fattori, siano bi

cii conver-

genti della frazione continua per√n.

Allora b2i mod n e sempre “piccolo”. Quindi tra i b2i mod n si trovano spesso interi chesono B-lisci. Quindi si puo sperare che presto si trovino bi1 , . . . , bit con (bi1 · · · bit)2 mod nun quadrato o piu precisamente bi1 · · · bit che vanno bene per l’algoritmo per fattorizzare conbasi di fattori.

Algoritmo 2.1.16 Dato: n che non e primo.Calcoliamo: due fattori di n.

1. Si sceglie una base di fattori B = {p0 = −1, p1, . . . , pr}.

2. La frazione continua per√n ci da a0, a1, a2, . . ..

3. Si calcola b0 = a0, b1 = a0a1 + 1, bi+1 = ai+1bi + bi−1.

4. Per i bi tali che b2i mod n e B-liscio si scrive b2i mod n = pei0

0 · · · peir

r finche si puo fareun prodotto (bi1 · · · bit)2 mod n = pe0

0 · · · perr con ei pari per ogni i. Si pone x = bi1 · · · bit

e y = pe02

0 · · · per2

r .

5. Se non si e sfortunati mcd(n, x+ y) e mcd(n, x− y) sono fattori di n.

Osservazione 2.1.17 L’algoritmo e basato su idee euristiche; non e garantito che riesce afattorizzare n. Pero, sappiamo che n e composto, quindi se non troviamo la fattorizzazionepossiamo riprovare con un B piu grande. Implementazioni pratiche hanno dimostrato che ilmetodo funziona abbastanza bene.

Esempio 2.1.18 (Fattorizzazione di numeri di Fermat)I numeri di Fermat sono della forma Fn = 22n

+ 1.Fermat era convinto che tutti questi numeri fossero primi. In realta Fn e primo per

0 ≤ n ≤ 4.Eulero pero dimostro che

F5 = 641 · 6700417.Nel 1880 Landry dimostro che

F6 = 274177 · 67280421310721.

Nel 1970 Morison e Brillhart, usando frazioni continue mostrarono che

F7 = 59649589127497217 · P22

dove P22 e un numero primo di 22 cifre.


Osservazione 2.1.19 Per calcolare la frazione continua per√n la seguente osservazione puo

aiutare. Per α ∈ R, α > 0 e m ∈ Z, m > 0, abbiamo che⌊

αm

⌋=⌊⌊α⌋m

⌋.

Dimostrazione. Scriviamo α = u+β con u intero e β ∈ R, 0 ≤ β < 1. Scriviamo u = qm+rcon 0 ≤ r < m. Quindi

⌊ αm

⌋=

⌊u

m+β

m

⌋=

⌊q +

r + β

m

⌋= q

perche r + β < m quindi r+βm < 1. D’altra parte

⌊⌊α⌋m

⌋=⌊ um

⌋=⌊q +

r

m

⌋= q.

�

Esempio 2.1.20 Vogliamo fattorizzare n = 33.

- Calcoliamo la frazione continua per√

33.

a0 = 5 x0 = x− a0 =√

33 − 5

x1 = 1√33−5

= 5+√

338

a1 = 1 x1 = x0 − a1 = −3+√

338

x2 = 1fx1

= 8−3+

√33

= 3+√

333

a2 = 2 x2 = x1 − a2 = −3+√

333

x3 = 3+√

338

a3 = 1 x3 = x2 − a3 = −5+√

338

x4 = 5 +√

33a4 = 10 . . .

- Calcoliamo i bi.

b0 = a0 = 5 b20 mod 33 = −8b1 = a0a1 + 1 = 6 b21 mod 33 = 3b2 = a2b1 + b0 = 17 b22 mod 33 = −8.

Quindi

x = b0b2 = 5 · 17 = 19 mod 33 e y = 8

e allora

mcd(x+ y, n) = mcd(27, 33) = 3 e mcd(x− y, n) = mcd(11, 33) = 11.


Esempio 2.1.21 Fattorizziamo n = 197209. Facendo i calcoli (considerando i bi modulo n)si ottiene

a0 = 444 b0 = 444 b20 mod n = −73 = −1 · 73a1 = 12 b1 = 5329 b21 mod n = 145 = 5 · 29a2 = 6 b2 = 31428 b22 mod n = −37 = −1 · 37a3 = 23 b3 = 159316 b23 mod n = 720 = 24 · 32 · 5a4 = 1 b4 = 191734 b24 mod n = −143 = −11 · 13a5 = 5 b5 = 131941 b25 mod n = 215 = 5 · 43a6 = 3 b6 = 193139 b26 mod n = −656 = −24 · 41a7 = 1 b7 = 127871 b27 mod n = 33 = 3 · 11a8 = 26 b8 = 165232 b28 mod n = −136 = −23 · 17a9 = 6 b9 = 133218 b29 mod n = 405 = 34 · 5

Quindi x = b3 ·b9 = 126308 mod n e y = 22 ·33 ·5 = 540. Quindi abbiamo che mcd(x+y, n) =991 e mcd(x− y, n) = 199.

Nel 1999, Brent, usando il metodo ECM (Elliptic Curve Method) ha trovato la fattoriz-zazione del numero di Fermat F10

45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252

dove P252 e un primo di 252 cifre.

2.1.5 Curve ellittiche

Sia k un campo e x3 + ax+ b ∈ k[x] con tre radici distinte. Allora

E(k) = {(x, y) ∈ k2 | y2 = x3 + ax+ b} ∪ {O}

dove O e un simbolo, e chiamato curva ellittica.

Osservazione 2.1.22 Sia f(x) = x3 + ax+ b. Allora f ha tre radici distinte se e solo se nonesiste α ∈ k con f(α) = f ′(α) = 0.

Sia P = (α, β) ∈ E(k) e vogliamo costruire la retta tangente a E(k) che passa per P . Perla pendenza facciamo la derivata di y2 = x3 + ax+ b, quindi

2ydy

dx= 3x2 + a = f ′(x).

Se f ha tre radici distinte non e possibile che β2 = f(α) = 0 e f ′(α) = 0 quindi la retta

tangente ha una pendenza ben definita che sara 3α2+a2β (β = 0 vuol dire retta verticale).

Scriviamo x3 + ax+ b = (x− α1)(x− α2)(x− α3) e definiamo

∆ = −∏

i<j

(αi − αj)2

che viene detto discriminante del polinomio x3 + ax + b. Questo ha tre radici distinte se esolo se ∆ 6= 0. Inoltre ∆ = 4a3 + 27b2.

Conclusione: y2 = x3 +ax+ b definisce una curva ellittica se e solo se ∆ = 4a3 +27b2 6= 0.Se k = R possiamo fare un grafico della curva. Si ottiene una cosa della seguente forma.


Il grafico e simmetrico rispetto all’asse x perche y2 = f(x). Quindi se (x0, y0) ∈ E(k)anche (x0,−y0) ∈ E(k).

Su E(k) possiamo definire un’addizione.

- l’elemento neutro e O quindi P +O = O + P = P per ogni P ∈ E(k).

- Se P1, P2 ∈ E(k), P1 6= P2 e P1, P2 6= O allora costruiamo la retta l per P1 e P2. La retta linterseca E(k) in un terzo punto P3 = (x3, y3) e poniamo P1 + P2 = (x3,−y3).

P1

P2

P3

P1 + P2

- Se P1 = P2 ∈ E(k), P1 6= 0, allora sia l la tangente a E(k) per P1 e poi si procede in modoanalogo.


P1

P3

P1 + P1

- Quando la retta e verticale allora la somma e O.

Teorema 2.1.23 L’insieme E(k) con la somma definita e un gruppo abeliano.

Qui non proviamo questo teorema; la cosa difficile da provare e che

(P1 + P2) + P3 = P1 + (P2 + P3).

Formule per l’addizione

Siano P1, P2 ∈ E(k), P1 6= P2, P1, P2 6= O e poniamo Pi = (xi, yi).

La retta per P1 e P2 e

y − y1 =y2 − y1

x2 − x1(x− x1).

Poniamo m = y2−y1

x2−x1e calcoliamo i punti di intersezione tra la retta e y2 = x3 + ax + b.

Avremo

(m(x− x1) + y1)2 = x3 + ax+ b ⇐⇒ x3 −m2x2 + ux+ v = 0

per opportuni u e v.

Due soluzioni di questa equazione sono x1 e x2 perche P1 e P2 sono sia sulla retta chesulla curva. Quindi

x3 −m2x2 + ux+ v = (x− x1)(x− x2)(x− x3) = x3 − (x1 + x2 + x3)x2 + . . .

quindi si vede che x1 + x2 + x3 = m2 e quindi

x3 = m2 − x1 − x2

y3 = m(x3 − x1) + y1

e dunque P1 + P2 = (m2 − x1 − x2,−m(x3 − x1) − y1).

Questa somma non dipende da a e b pero i punti P1 e P2 dipendono da a e b.

Se P1 = P2 consideriamo la derivata rispetto a x di y2 = x3 + ax + b. Avremo 2y dydx =

3x2 + a.


- Se y1 6= 0 allora

m =3x2

1 + a

2y1

quindi la retta l sara y = m(x− x1) + y1. Segue che P1 + P1 = (x3,−y3) con

x3 = m2 − 2x1

y3 = m(x3 − x1) + y1.

- Se y1 = 0 allora P1 + P1 = O. (Osserviamo che non e possibile avere y1 = 3x21 + a = 0.)

Esempio 2.1.24 Prendiamo y2 = x3 + 17 e P1 = (−1, 4). Avremo

m =3(−1)2 + 0

8=

3

8

x3 =9

64+ 2 =

137

64

y3 =3

8

(137

64+ 1

)+ 4 =

2651

512.

Quindi P1 + P1 =(

13764 ,−2651

512

).

2.1.6 Fattorizzazione con curve ellittiche

Sia p un primo. Definiamo

Ap =

{α

β∈ Q | p non divide β

}.

N.B. Se p non divide β allora esiste γ ∈ Z con γβ = 1 mod p. Scriviamo γ = β−1 mod p.

Definiamo ψp : Ap → Fp, con ψp

(αβ

)= αβ−1 mod p.

Siano a, b ∈ Z tale che 4a3 + 27b2 6= 0 mod p. Allora

E(Fp) = {(x, y) ∈ F2p | y2 = x3 + ax+ b} ∪ {O}

e una curva ellittica su Fp.Ma anche

E(Q) = {(x, y) ∈ Q | y2 = x3 + ax+ b} ∪ {O}e una curva ellittica.

Definiamo ϕp : E(Q) → E(Fp) nel seguente modo. Sia P =(

αβ ,

γδ

)∈ E(Q). Se p non

divide β e p non divide δ allora

ϕp(P ) =

(ψp

(α

β

), ψp

(γδ

))

altrimenti ϕp(P ) = O.

Teorema 2.1.25 L’applicazione ϕp e un omomorfismo di gruppi. In altre parole ϕp(P1 +P2) = ϕp(P1) + ϕp(P2).


Qui proviamo solo un caso speciale di questo teorema.

Definizione 2.1.26 Sia p un primo e P =(

u1

v1, u2

v2

)∈ Q2. Allora P e chiamato buono per

p se p non divide v1 e p non divide v2.

Lemma 2.1.27 Sia E(k) = {(x, y) | y2 = x3 + ax+ b}∪ {O} una curva ellittica con a, b ∈ Z

e p > 2 un primo tale che p non divide ∆ = 4a3 + 27b2. Sia ϕp : E(Q) → E(Fp) la riduzionemodulo p. Siano P1, P2 ∈ E(Q) due punti buoni per p. Allora ϕp(P1 +P2) = ϕp(P1)+ϕp(P2).

Dimostrazione. Sia Pi = (xi, yi). Qui scriviamo anche x mod p per ψp(x).

- Sia P1 6= P2, ϕp(P1) 6= ϕp(P2) e x1 mod p 6= x2 mod p. In questo caso si usano lestesse formule sia su Q che su Fp per calcolare la somma. Visto che modp e moltiplicativo eadditivo il risultato e uguale. Questo raggionamento anche vale quando P1 = P2.

- Sia P1 6= P2 e x1 mod p = x2 mod p. Scriviamo x2 = x1 + prx con x ∈ Q, x mod p 6= 0.Allora y2

1 = y22 mod p perche x3

1 +ax1 + b = x32 +ax2 + b mod p e quindi y1 = ±y2 mod p. Poi

y22 = x3

2 + ax2 + b

= (x1 + prx)3 + a(x1 + prx) + b

= x31 + ax1 + b+ (3x2

1 + a)prx+ ∗pr+1

= y21 + (3x2

1 + a)prx+ ∗pr+1

per un’appropriata quantita ∗.Quindi

(y2 + y1)(y2 − y1) = (3x21 + a)prx+ ∗pr+1.

Adesso distinguiamo due casi. Nel primo abbiamo y1 = y2 mod p. In quel caso

y2 − y1 = (3x21 + a)prx(y2 + y1)

−1 + ∗pr+1

per un opportuno ∗.Per calcolare P1 + P2 in E(Q) usiamo

m =y2 − y1

x2 − x1=

3x21 + a

y2 + y1+ ∗p

dove x2 − x1 = prx.

Quindi m mod p =3x2

1+a

2y1mod p che e esattamente l’m che si usa per calcolare ϕp(P1) +

ϕp(P2). Quindi

ϕ(P1 + P2) = ϕp(P1) + ϕp(P2).

Se y1 = −y2 mod p allora abbiamo che y2 − y1 6= 0 mod p (altrimenti entriamo nel casoprecedente, visto che p > 2). Quindi

m =y2 − y1

prx.

Visto che r > 0 abbiamo che ϕp(P1 + P2) = O, che e uguale a ϕp(P1) + ϕp(P2). �


L’idea del metodo per fattorizzare interi con curve ellittiche il la seguente. Il gruppoE(Fp) e finito quindi per P ∈ E(Fp) esiste k con

P + . . . + P︸︷︷︸k

= O.

Sia Q ∈ E(Q) con ϕp(Q) = P . Allora per il Teorema 2.1.25

ϕ(Q+ . . . +Q︸︷︷︸k

) = P + . . .+ P︸︷︷︸k

= O.

Quindi kQ = Q+ . . .+Q e uguale a 0 oppure ha coordinate con denominatore divisibile perp.

Algoritmo 2.1.28 Dato: un numero composto n.Calcoliamo: un fattore di n

1. Si sceglie una curva data da y2 = x3 + ax+ b con un punto P su E(Q).

2. Sia d = mcd(n, 4a3 + 27b2). Se d = n si sceglie un’altra curva. Se d > 1 e d < nabbiamo un divisore di n.

3. Assumiamo d = 1. Poniamo k = mcm(2, 3, . . . ,K) per un certo K.

4. Calcoliamo kP =(

u1

v1, u2

v2

). Sia di = mcd(vi, n). Se di e un divisore piu grande di 1 e

minore di n allora un fattore e trovato. Altrimenti si riprova con K piu grande o conun’altra curva.

N.B. Sappiamo che n non e primo. Il metodo funziona se:

- sia p un primo che divide n;

- se l’ordine di ϕp(Q) divide k allora ϕp(kQ) = kϕp(Q) = O e quindi se kQ 6= O allora pdivide il denominatore di u o di v.

Teorema 2.1.29 (di Hasse) Si ha

p+ 1 − 2√p ≤ |E(Fp)| ≤ p+ 1 + 2

√p.

Osservazione 2.1.30 Se |E(Fp)| divide k allora troviamo p. Per esempio quando K ≥p+ 1 + 2

√p.

Esempio 2.1.31 Supponiamo che 61 divida n. Sia Ea la curva y2 = x3 + ax + 3 − a eP = (1, 2). Avremo

a |Ea(F61)| ordine di (P mod 61)−4 68 68−3 54 9−2 76 38−1 69 690 48 121 48 42 66 333 72 64 67 67


Ora 4P = O ∈ E1(Q) e 6P =(

5182560116208676 , ∗

)∈ E3(Q) e 61 divide 16208676.

Osservazione 2.1.32 E’ sufficiente conoscere kP modulo n. Cioe se rP =(

u1

v1, u2

v2

)e se

mcd(vi, n) 6= 1, allora il fattore e trovato. Altrimenti se mcd(vi, n) = 1 allora esistono ci, di

con civi + din = 1 e allora ui

vimod n = uici mod n.

Esempio 2.1.33 Fattorizziamo n = 39. Abbiamo che ∆ = 31 e mcd(31, 39) = 1. Prendiamocome E la curva y2 = x3 + x− 1 e P = (1, 1). Sia k = 6.

Abbiamo che 2P = (2,−3). Calcoliamo 4P . Avremo

m =3x2

1 + a

y1=

12 + 1

−6= −13

6

e poiche mcd(6, 39) = 3 allora abbiamo trovato un fattore.

Esempio 2.1.34 Fattorizziamo 185 con la curva dell’Esempio 2.1.33 e k = 8. Si ha ∆ = 31e mcd(31, 185) = 1 quindi y2 = x3 +x− 1 definisce una curva ellittica modulo ogni primo chedivide n.

Abbiamo che 2P = (2,−3).Calcoliamo 4P . Si ha m = −13

6 . Ora

185 = 1 · 185 + 0 · 66 = 0 · 185 + 1 · 65 = 1 · 185 − 30 · 61 = −1 · 185 + 31 · 6

quindi 6−1 mod 185 = 31. Segue che

m mod 185 = −13 · 31 mod 185 = 152 mod 185.

Quindi si ha

x3 = m2 − 2x1 = 1522 − 2 · 2= 160 mod 185

y3 = m(x3 − x1) − y1 = 152(160 − 2) − 3

= −37 mod 185.

Quindi 4P = (160, 37) mod 185.Calcoliamo ora 8P . Abbiamo

m =3x2

1 + a

2y1=

3 · 1602 + 1

74.

Ora185 = 1 · 185 + 0 · 7474 = 0 · 185 + 1 · 7437 = 1 · 185 − 2 · 740 = −2 · 185 + 5 · 74

quindi mcd(185, 74) = 37 e dunque 185 = 5 · 37.

2.2 Esercizi 41

2.1.7 Complessita

- L’algoritmo che prova k = 2, 3, . . . ,√n come divisori ha complessita O(p) (ordine di p),

dove p e il fattore piu piccolo di n. Ma O(p) = O(√n). Inoltre

√n = n

1

2 = exp(

12 log n

)e

log n ∼= “numero di cifre di n” = complessita di n. Quindi exp(

12 log n

)e esponenziale.

- Il metodo curve ellittiche ha complessita stimata O(exp√

log p log(log p)) dove p e ilfattore piu piccolo di n. Questo e “subesponenziale”.

- Il metodo con le frazioni continue ha complessita stimata O(exp√

2 log p log(log p)).

- Due altri metodi famosi sono: il crivello quadratica ha complessitaO(exp√

log n log(log n)),il crivello dei campi di numeri con complessita O(exp (log)1/3(log(log p))2/3).

2.2 Esercizi

1. Fattorizzare 203 e 899 con il metodo di Fermat.

2. In questo esercizio vogliamo trovare una fattorizzazione di n = 8616460799 con il metododi Fermat. Quindi vogliamo trovare t > s tali che t2 − s2 = n.

(a) Abbiamo n mod 3 = 2. Provare che k2 mod 3 e 0 o 1 per k ∈ Z. Provare che set2 mod 3 = 1, allora t2 − n non puo essere un quadrato. Concludere che t deveessere divisibile per 3.

(b) Abbiamo n mod 8 = 7. Provare che k2 mod 8 e 0,1,4. Provare che se t2 − n e unquadrato allora t2 = 0 mod 8. Concludere che t deve essere divisibile per 4.

(c) Provare che t deve essere divisibile per 12.

(d) Adesso provare per t i multipli di 12, maggiori di ⌈√n⌉. Scrivere n come unprodotto di interi piu piccoli.

(e) L’economista inglese W. S. Jevons (1835-1882) ha scritto: Given any two numbers,we may by a simple and infallible process obtain their product, but it is quiteanother matter when a large number is given, to determine its factors. Can thereader say what two numbers multiplied together produce the number 8616460799?I think it unlikely that anyone but myself will ever know.

3. Trovare i primi 7 convergenti della frazione continua per√

5.

4. Fattorizzare 299, 341, 1537 e 1139 con il metodo delle frazioni continue.

5. Sia a > 1 un intero, e

θ =a+

√a2 + 4

2.

Provare che nella frazione continua per θ abbiamo a = a0 = a1 = a2, . . ..

6. Sia

x =1 +

√5

2.

Siano a0, a1, . . . i numeri che vengono fuori dalla frazione continua per x.

(a) Provare che ai = 1 per i ≥ 0.


(b) Sia Fn l’n-esimo numero di Fibonacci (cioe F0 = 1, F1 = 1, Fn+1 = Fn + Fn−1).Provare che i convergenti della frazione continua per x sono Fn+1

Fnper n ≥ 0.

7. Consideriamo la curva ellittica con equazione y2 = x3 + x − 1. Sia P = (1, 1) ∈ E.Calcolare 3P = P + P + P .

8. In questo esercizio vogliamo fattorizzare n = 65 = 5 · 13 con il metodo delle curveellittiche. Sia E la curva ellittica con equazione y2 = x3 + 2x+ 1 e P = (1, 2).

(a) Controllare che l’equazione definisce una curva ellittica modulo ogni primo chedivide n.

(b) Calcolare tutti i punti di E(F5) (suggerimento: fare una tabella dei quadrati mo-dulo 5, e una tabella dei x3 +2x+1 per x ∈ F5). Provare che kϕ5(P ) = O implicache k e divisibile per 7. (Qui ϕ5(P ) e la riduzione di P modulo 5.)

(c) Calcolare tutti i punti di E(F13). Provare che 4ϕ13(P ) = O.

(d) Calcolare 4P modulo n, e fattorizzare n.

9. Di nuovo consideriamo n = 65, ma adesso consideriamo la curva con equazione y2 =x3 + 3x+ 2 e P = (2, 4).

(a) Controllare che l’equazione definisce una curva ellittica modulo ogni primo chedivide n.

(b) Calcolare tutti i punti di E(F5). Provare che kϕ5(P ) = O se e solo se che k edivisibile per 5.

(c) Calcolare 5P modulo n e fattorizzare n.

10. Fattorizzare n = 115 con il metodo delle curve ellittiche. (Si puo usare la curva y2 =x3 + 2x− 3 e P = (2, 3).)

Capitolo 3

Fattorizzazione di polinomi

Vogliamo fattorizzare polinomi in k[x] dove k e un campo.Gli algoritmi dipendono dalla scelta di k. Studiamo algoritmi per il caso k = Fq dove

q = pn, p primo, e k = Q.

3.1 Alcuni fatti generali sui polinomi

Lemma 3.1.1 Dati f, g ∈ k[x] esistono unici q, r ∈ k[x] con deg(r) < deg(g) e f = qg + r(divisione con resto).

Lemma 3.1.2 Sia I ⊂ k[x] un ideale. Allora I e generato da un elemento, cioe esiste g ∈ Icon I = {fg | f ∈ k[x]}.

Dimostrazione. Sia g ∈ I un elemento non nullo di grado minimo. Se h ∈ I scriviamoh = qg + r con deg(r) < deg(g). Questo implica r ∈ I quindi r = 0 e h = qg. �

Lemma 3.1.3 Siano f1, f2 ∈ k[x]. Allora esiste un unico monico g ∈ k[x] con

1) g divide f1, f2;

2) se h divide f1, f2 allora divide g.

Dimostrazione. Sia I ⊂ k[x] l’ideale generato da f1, f2, cioe I = {h1f1 + h2f2 | hi ∈ k[x]}.Allora I e generato da un monico g (di grado minimo). Ora f1, f2 ∈ I implica che g dividef1 e f2.

Se h divide f1, f2 allora scriviamo g = h1f1+h2f2 (visto che g ∈ I = 〈f1, f2〉) e concludiamoche h divide g.

Per dimostrare l’unicita, sia g′ ∈ k[x] con le stesse proprieta di g. Allora, per 1) e 2), g′

divide g. Analogamente g divide g′. Essendo g e g′ monici segue che g = g′. �

Definizione 3.1.4 Il polinomio g e chiamato massimo comun divisore di f1 e f2.

Si vede dalla prova del Lemma 3.1.3 che esistono h1, h2 tali che h1f1 + h2f2 = g. Comeper gli interi abbiamo un algoritmo di Euclide per calcolare il massimo comune divisore dif1, f2. E’ basato sul seguente lemma.

44 Fattorizzazione di polinomi

Lemma 3.1.5 Scriviamo f1 = qf2 + r con deg(r) < deg(f2). Allora si ha mcd(f1, f2) =mcd(f2, r).

Dimostrazione. Poniamo

D1 = {h ∈ k[x] | h divide f1, f2} e D2 = {h ∈ k[x] | h divide f2, r}.

Allora D1 = D2. Quindi anche l’elemento monico di grado massimale di D1 e D2 e uguale. �

Per calcolare mcd(f1, f2) si rimpiazza (f1, f2) con (f2, r) e cosı via. Ad un certo punto sitrova (g, 0) e mcd(g, 0) = g.

Esempio 3.1.6 Siano f1 = x7 + 1, f2 = x4 + x2 + x ∈ F2[x]. Abbiamo

f1 = (x3 + x+ 1)f2 + x3 + x+ 1.

Posto f3 = x3 + x+ 1 si ha

f2 = xf3 + 0

quindi mcd(f1, f2) = mcd(f2, f3) = mcd(f3, 0) = f3.

N.B. Un polinomio h ∈ k[x] e chiamato irriducibile se h = ab con a, b ∈ k[x] implica chea oppure b sta in k.

Teorema 3.1.7 Sia f ∈ k[x], allora esistono unici c ∈ k, f1, . . . , fr monici, irriducibili ediversi in k[x] e e1, . . . , er ∈ Z>0 con f = cf e1

1 · · · f err .

Dimostrazione. Se f e irriducibile non c’e niente da fare. Altrimenti sara f = ab dove a, bsono polinomi tali che deg(a),deg(b) < deg(f). Allora per induzione a e b sono prodotti diirriducibili, e quindi anche f .

Per dimostrare l’unicita supponiamo che f = c1fe1

1 · · · f err = c2g

d1

1 · · · gdmm con ogni gi

ancora irriducibile e monico.

Innanzitutto si vede che c1 e c2 sono il coefficiente di testa di f , e percio c1 = c2.

Fatto: sia a ∈ k[x] irriducibile e a divida bc con b, c ∈ k[x]. Allora a divide b oppure adivide c. (Infatti, se a non divide b allora mcd(a, b) = 1 quindi esistono h1, h2 con h1a+h2b = 1quindi c = h1ac+ h2bc e quindi a divide c.)

Da questo fatto segue che f1 divide un gi. Ma ogni gi e irriducibile e monico quindih1 = gi e quindi questi elementi cancellano. Usando l’induzione concludiamo che l’insieme{f1, . . . , fr} = {g1, . . . , gm} e gli esponenti sono uguali. �

Problema. Dato f ∈ k[x] monico trovare f1, . . . , fr irriducibili, monici e distinti tali chef = f e1

1 · · · f err .

3.2 L’algoritmo di Berlekamp

Definizione 3.2.1 Sia f ∈ k[x] monico e f = f e1

1 · · · f err con fi irriducibile e monico per

ogni i. Allora gli f ei

i sono chiamati fattori primari di f .

3.2 L’algoritmo di Berlekamp 45

Lemma 3.2.2 Sia f ∈ Fq[x] monico e v ∈ Fq[x] con vq = v mod f . Allora

f =∏

a∈Fq

mcd(f, v − a).

Dimostrazione. In Fq[Y ] abbiamo

Y q − Y =∏

a∈Fq

(Y − a)

(perche aq = a per ogni a ∈ Fq). Sostituiamo Y con v e otteniamo

vq − v =∏

a∈Fq

(v − a).

Ma vq − v e divisibile per f quindi f = mcd(f, vq − v).Fatto: siano p, q, r ∈ k[x] con mcd(q, r) = 1. Allora

mcd(p, qr) = mcd(p, q)mcd(p, r).

Questo si puo provare nel seguente modo. Sia g un polinomio irriducibile che divide qr.Allora g divide q o r, ma non entrambi (questo si vede scrivendo la fattorizzazione di q equella di r; in uno di quelle deve apparire g). Questo implica che un polinomio qualsiasi gche divide qr puo essere scritto come g = g1g2, con g1 divide q, e g2 divide r. Sia A l’insiemedei polinomi che dividono qr. Siano B1, B2 rispettivamente gli insiemi dei divisori di q e r.Allora segue che A = B1B2, che implica la tesi.

Osserviamo che mcd(v − a, v − b) = 1 se a 6= b, a, b ∈ Fq. Infatti se g divide v − a e v − ballora g divide b− a 6= 0 con b− a ∈ Fq.

Segue che

f = mcd(f, vq − v)

= mcd(f,∏

a∈Fq

(v − a))

=∏

a∈Fq

mcd(f, v − a).

�

Notazione. Con Fq[x]/(f) denotiamo l’anello quoziente Fq[x] modulo l’ideale generato daf .

Se f = xn + . . . + a0 allora ogni elemento di Fq[x]/(f) ha un rappresentante unico dellaforma b0 + b1x+ . . . + bn−1x

n−1.

Lemma 3.2.3 Sia f ∈ Fq[x] monico e sia

V = {v ∈ Fq[x]/(f) | vq − v mod f}.

Scriviamo f = f e1

1 · · · f err dove gli fi sono irriducibili distinti. Allora V e uno spazio vettoriale

su Fq di dimensione r.


Dimostrazione. Siano v,w ∈ V , allora

(v + w)q = vq + wq = v + w mod f

e quindi v +w ∈ V .Inoltre sia α ∈ Fq, allora

(αv)q = αqvq = αvq = αv mod f

quindi αv ∈ V .Quindi V e uno spazio vettoriale su Fq.Siano ora R1, . . . , Rs anelli. Ricordiamo che la somma diretta di anelli R = ⊕s

i=1Ri el’insieme che consiste di (r1, . . . , rs) con ri ∈ Ri e tale che

(r1, . . . , rs) + (r′1, . . . , r′s) = (r1 + r′1, . . . , rs + r′s)

e(r1, . . . , rs)(r

′1, . . . , r

′s) = (r1r

′1, . . . , rsr

′s).

Si ha che R e un anello.Per il Teorema cinese dei resti per anelli polinomiali, esiste un isomorfismo di anelli

ϕ : Fq[x]/(f) → ⊕ri=1Fq[x]/(f

ei

i ). Qui ϕ(h mod f) = (h mod f e1

1 , . . . , h mod f err ).

Per v ∈ V scriviamo ϕ(v) = (v1, . . . , vr). Quindi

v ∈ V ⇔ vq = v mod f ⇔ vqi = vi mod f ei

i .

Per il Lemma 3.2.2 abbiamo che

f ei

i =∏

a∈Fq

mcd(f ei

i , vi − a). (3.1)

Ma vi − a e vi − b sono coprimi per a, b ∈ Fq e a 6= b. Segue che in (3.1) abbiamo soltantofattori di vi − a per un unico a ∈ Fq, oppure f ei

i = mcd(f ei

i , vi − a), oppure f ei

i divide vi − a.Quindi vi = a mod f ei

i e quindi ϕ(V ) ⊂ Fq ⊕ . . . ⊕ Fq dove Fq ⊂ Fq[x]/(fei

i ) sono i polinomicostanti.

Ma aq = a per ogni a ∈ Fq quindi Fq ⊕ . . .⊕ Fq ⊂ ϕ(V ).Segue che ϕ(V ) = Fq ⊕ . . . ⊕ Fq (r addendi), implica che V e uno spazio vettoriale di

dimensione r. �

Ora presentiamo l’algoritmo di Berlekamp per trovare i fattori primari di f ∈ Fq[x] con fmonico.

Algoritmo 3.2.4 Dato: f ∈ Fq[x], monico.Calcoliamo: i fattori primari di f .

1. Sia {v1 = 1, v2, . . . , vr} una base di V = {v ∈ Fq[x]/(f) | vq = v mod f}.

2. Poniamo P = {f} e per j = 2, . . . , r facciamo

2a) rimpiazziamo ogni h ∈ P con gli elementi non banali dell’insieme {mcd(h, vj − a) |a ∈ Fq}.

3.2 L’algoritmo di Berlekamp 47

3. Il risultato e P .

Lemma 3.2.5 L’algoritmo di Berlekamp restituisce i fattori primari di f .

Dimostrazione. Dobbiamo dimostrare che

- f e il prodotto degli elementi di P ;

- gli elementi di P sono coprimi;

- gli elementi di P sono una potenza di un irriducibile.

Il prodotto degli elementi di P rimane sempre uguale perche

h =∏

a∈Fq

mcd(h, vj − a).

Infatti, abbiamo vqj = vj mod f , ma gli h ∈ P sono fattori di f quindi vq

j = vj mod h. Quindipossiamo applicare il Lemma 3.2.2.

Inoltre e sempre vero che gli elementi di P sono coprimi perche se h ∈ P e rimpiazzatocon diversi fattori quelli sono fattori di vj − a per diversi a e quindi coprimi.

Ora sia P l’insieme finale, e h ∈ P . Assumiamo che h non e una potenza di un irriducibile.Allora da quello detto sopra segue che h e divisibile per un f ei

i e un fej

j . Per semplicitaassumiamo i = 1 e j = 2.

Osserviamo che per g ∈ P e 1 ≤ j ≤ r abbiamo che esiste aj ∈ Fq con vj = aj mod g.Questo e vero dopo il passo 2a) dove e trattato j. Infatti dopo quel passo ogni elemento diP e fattore di un vj − a per un certo a ∈ Fq. Ma se vj = aj mod g0 e g0 e rimpiazzato conalcuni fattori g′0, allora vj = aj mod g′0. Concludiamo che esiste aj ∈ Fq con vj = aj mod hper 1 ≤ j ≤ r.

Adesso sia v ∈ V e scriviamo v =∑r

j=1 βjvj, βj ∈ Fq. Allora

v =r∑

j=1

βjaj mod h.

Posto av =∑r

j=1 βjaj abbiamo v = av mod h, av ∈ Fq.Visto che f e1

1 , f e2

2 dividono h abbiamo che v = av mod f e1

1 e v = av mod f e2

2 . Ma ϕ : V →Fq ⊕ . . .⊕ Fq con ϕ(v) = (v mod f e1

1 , . . . , v mod f err ) e un isomorfismo.

Ma ϕ(v) = (av , av, ∗, . . . , ∗), cioe le prime due componenti sono sempre uguali. Questoimplica che ϕ non e un isomorfismo e quindi otteniamo una contraddizione. �

Problema rimasto. Dato f ∈ Fq[x], f = ge con g irriducibile, trovare g ed e.Si calcola f ′ = d

dxf = eg′ge−1. Abbiamo due casi:1) f ′ = 0. Dico che f e un polinomio in xp dove q = pm, p primo.Gli esponenti di x che appaiono in f sono divisibili per p quindi f = h(xp) = h1(x)

p.Calcoliamo h1 che e ancora una potenza di g e continuiamo.

2) f ′ 6= 0. Allora g = fmcd(f,f ′) dove mcd(f, f ′) = ge−1.

Esempio 3.2.6 Sia f = x4 + x3 + x + 1 ∈ F2[x]. Scriviamo v ∈ F2[x]/(f) come v =a0 + a1x+ a2x

2 + a3x3, ai ∈ F2.


Poiche a2i = ai allora v2 = a0 + a1x

2 + a2x4 + a3x

6.Ora, modulo f , abbiamo

x4 = x3 + x+ 1

x5 = x4 + x2 + x = x3 + x+ 1 + x2 + x

= x3 + x2 + 1

x6 = x4 + x3 + x = x3 + x+ 1 + x3 + x

= 1

quindi

v2 = a0 + a1x2 + a2(x

3 + x+ 1) + a3 mod f

= a0 + a2 + a3 + a2x+ a1x2 + a2x

3 mod f

e quindi

a0 + a2 + a3 = a0

a2 = a1

a1 = a2

a2 = a3

⇐⇒ a1 = a2 = a3

quindi una base di V e {v1 = 1, x+ x2 + x3}.Abbiamo trovato r = 2Nel passo 2a) rimpiazziamo f con

h1 = mcd(f, x+ x2 + x3) = x2 + x+ 1

h2 = mcd(f, 1 + x+ x2 + x3) = x2 + 1.

Quindi troviamo P = {h1, h2}. Abbiamo h′1 = 1, e segue che mcd(h1, h′1) = 1 e dunque h1 e

irriducibile. Analogamente h′2 = 0 implica h2 = (x+ 1)2 e (x+ 1)′ = 1 quindi e irriducibile.Concludiamo che f = (x+ 1)2(x2 + x+ 1) e la fattorizzazione di f .

3.3 Algoritmo di Cantor-Zassenhaus (1981)

L’algoritmo di Berlekamp ha un grande svantaggio in quanto bisogna calcolare mcd(f, v− a)per a ∈ Fq. Potenzialmente questo costa tanto lavoro.

Assumiamo q dispari.

Lemma 3.3.1 Sia γ ∈ F∗q , allora γ

q−1

2 = ±1. Inoltre γq−1

2 = 1 se e solo se γ e un quadrato

in Fq e γq−1

2 = −1 se e solo se γ non e un quadrato.

Dimostrazione. Sia α ∈ F∗q un elemento primitivo, αq−1 = 1, αk 6= 1 per k < q− 1. Quindi

γ = αi implica

γq−1

2 =(α

q−1

2

)i.

Osservazione 3.3.2 Sia ha che(α

q−1

2

)2= 1 implica α

q−1

2 = ±1 (ci sono soltanto due radici

di 1 in Fq) ma αq−1

2 6= 1 quindi αq−1

2 = −1.

3.4 Fattorizzazione di polinomi in Q 49

Quindi se γ e un quadrato allora γ = α2k e quindi γq−1

2 =(αq−1

)k= 1. Se γ non e un

quadrato allora γ = α2k+1 quindi γq−1

2 = αq−1

2 (αq−1)k = −1. �

Consideriamo lo spazio

V = {v ∈ Fq[x]/(f) | vq = modf}.

Sia v ∈ V e vediamo V dentro Fq[x]. Allora

vq − v = v(v

q−1

2 − 1)(

vq−1

2 + 1).

Osservazione 3.3.3 Questi fattori sono coprimi.

Si ha

f = mcd(f, vq − v) = mcd(f, v)mcd(f, vq−1

2 − 1)mcd(f, vq−1

2 + 1).

Questa fattorizzazione di f e banale (cioe f = f ·1 ·1) se e solo se f divide uno tra v, vq−1

2 −1,

vq−1

2 + 1.

Possiamo assumere che deg(v) < deg(f) quindi f non divide v.

Sia ϕ : Fq[x]/(f) → ⊕ri=1Fq[x]/(f

ei

i ), l’isomorfismo dove f ei

i sono i fattori primari di f .Allora ϕ(V ) = ⊕r

i=1Fq implica ϕ(v) = (a1, . . . , ar), ai ∈ Fq.

Adesso f divide vq−1

2 − 1 se e solo se vq−1

2 = 1 mod f e quindi se e solo se ϕ(v)q−1

2 =

(1, . . . , 1) oppure aq−1

2

i = 1 per ogni i. Per il Lemma 3.3.1 si ha che ai ∈ F∗q e un quadrato

per ogni i.

Analogamente f divide vq−1

2 + 1 se e solo se ai ∈ F∗q non e un quadrato per ogni i.

Poniamo

C = {(a1, . . . , ar) ∈ F∗qr | ai e un quadrato ∀i}

∪ {(a1, . . . , ar) ∈ F∗qr | ai non e un quadrato ∀i}.

Si ha che

|C| =

(q − 1

2

)r

+

(q − 1

2

)r

= 2

(q − 1

2

)r

.

Se prendiamo v ∈ V casualmente (distribuzione uniforme) allora la probabilita che la fatto-rizzazione vada male e data da

P(ϕ(v) ∈ C) =|C||V | =

2(

q−12

)r

qr= 2

(1 − 1

q

2

)r

<1

2.

Quindi se scegliamo v casualmente k volte la probabilita di non trovare una fattorizzazione e

minore di(

12

)k.

3.4 Fattorizzazione di polinomi in Q

Prima vediamo che fattorizzare polinomi in Q si riduce a fattorizzare in Z[x].


Definizione 3.4.1 Sia f ∈ Z[x], f = a0 + a1x+ . . . + anxn, ai ∈ Z. Allora

c(f) = mcd(a0, a1, . . . , an)

e chiamato contenuto di f .

Lemma 3.4.2 Siano f, g ∈ Z[x] con c(f) = c(g) = 1, allora c(fg) = 1.

Dimostrazione. Supponiamo che c(fg) > 1. Allora esiste un primo p che divide tutti icoefficienti di fg.

Per h ∈ Z[x] scriviamo f per il polinomio h mod p che e un polinomio in Fp[x]. Allora0 = fg = f g 6= 0 perche f 6= 0 6= g in quanto hanno contenuto 1. �

Lemma 3.4.3 (Gauss) Siano f, g ∈ Z[x]. Allora c(fg) = c(f)c(g).

Dimostrazione. Scriviamo a = c(f), b = c(g). Allora fa ,

gb ∈ Z[x]. Ma

fg = abf

a

g

b⇒ c(fg) = c

(abf

a

g

b

)= ab · c

(f

a

g

b

).

Ma c(

fa

)= c

( gb

)= 1 quindi, per il Lemma 3.4.2, c

(fa

gb

)= 1 quindi c(fg) = ab. �

Teorema 3.4.4 Sia f ∈ Z[x] e supponiamo che esistano g, h ∈ Q[x] con f = gh. Alloraesistono a, b ∈ Q tali che ag, bh ∈ Z[x] e f = (ag)(bh).

In altre parole ogni fattorizzazione di f in Q[x] viene da una fattorizzazione in Z[x].

Dimostrazione. Possiamo assumere che c(f) = 1 (altrimenti dividiamo per c(f)). Sianoa, b ∈ Q tali che ag, bh ∈ Z[x] e c(ag) = c(bh) = 1. Abbiamo

abf = (ag)(bh) ∈ Z[x] e c(abf) = c(ag)c(bh) = 1.

Se ab = st , se t > 1, allora ogni coefficiente di f e divisibile per t perche s

tf ∈ Z[x]. Mac(f) = 1 quindi non e possibile. Segue che t = 1.

Ora c(abf) = c(sf) = 1 quindi s = ±1. Quindi (ag)(bh) = ±f . Se questo e −f allorarimpiazziamo a con −a e otteniamo f = (ag)(bh). �

Quindi per fattorizzare un f ∈ Q[x] possiamo fare alcune riduzioni

- assumere f ∈ Z[x] (altrimenti moltiplichiamo per s ∈ Z);

- non cambia niente se cerchiamo i fattori in Z[x] (per il Teorema 3.4.4);

- assumiamo che f sia libero di quadrati. Altrimenti scriviamo f = g2h e allora f ′ = 2gg′h+g2h′ e quindi g divide mcd(f, f ′). Quindi possiamo fattorizzare mcd(f, f ′) e f

mcd(f,f ′) .

Idea. Fattorizziamo f mod p, p primo, e solleviamo i fattori su Z. Questo processo sichiama sollevamento di Hensel.


3.4.1 Sollevamento di Hensel

Teorema 3.4.5 (Hensel) Sia f ∈ Z[x] e p un primo. Siano g, h ∈ Z[x] con

- deg(g) + deg(h) = deg(f);

- mcd(g, h) = 1 mod p;

- f = gh mod pk per un certo intero k > 0.

Allora esistono g, h ∈ Z[x] con

- deg(g) = deg(g), deg(h) = deg(h);

- g = g mod pk, h = h mod pk;

- f = gh mod pk+1.

Dimostrazione. Poniamo g = g + pku, h = h+ pkv per certi u, v ∈ Z[x].Controlliamo la terza proprieta. Abbiamo

f − gh = f − gh− pkvg − pkuh− p2kuv

e questo deve essere 0 modulo pk+1.N.B. Si ha che f − gh e divisibile per pk.Cerchiamo u e v tali che

f − gh

pk− vg − uh = 0 mod p.

Poniamo e = f−ghpk .

Sappiamo che mcd(g, h) = 1 mod p. Quindi esistono a, b ∈ Z[x] con ag + bh = 1 mod p.Quindi eag + ebh = e mod p.

Andrebbe bene con v = ea e u = eb ma questo potrebbe aumentare il grado. Aggiustiamoquindi le cose per eb. Scriviamo eb = qg + r con deg(r) < deg(g). Allora

eag + (qg + r)h = e mod p ⇔ (ea+ qh)g + rh = e mod p.

Proviamo allora con v = ea + qh mod p e u = r mod p. Naturalmente, ci interessanosoltanto u e v modulo p.

Quindi la seconda e la terza proprieta sono soddisfatte. Bisogna controllare i gradi.Abbiamo

deg(u) = deg(r) < deg(g) ⇒ deg(g) = deg(g).

Poiche e = f−ghpk allora deg(e) ≤ deg(f).

Inoltre uh + vg = e mod p ma deg(uh) < deg(f) perche deg(u) < deg(g). Quindideg(vg mod p) ≤ deg(f). Segue che

deg(v mod p) ≤ deg(h) ⇒ deg(h) = deg(h).

�

La prova del precedente teorema da un algoritmo per costruire g, h. Bisogna calcolare


- e = f−ghpk ;

- a, b con ag + bh = 1 mod p (algoritmo di Euclide esteso);

- q, r con eb = qg + r e deg(r) < deg(g) (divisione con resto);

- u = r mod p e v = ea+ qh mod p.

Allora g = g + pku e h = h+ pkv.

Esempio 3.4.6 Sia f = x4 + 2x3 − 3x2 − 4x− 1, g = x2 + 1 e h = x2 + 2x+ 2. Abbiamo che

gh = x4 + 2x3 + 3x2 + 2x+ 2 = f mod 3

quindi

e =f − gh

3= −2x2 − 2x− 1 = x2 + x+ 2 mod 3.

Possiamo fare i calcoli modulo p perche u e v ci interessano solo modulo p. In particolaree, a, b, q, v possono essere calcolati modulo p. Abbiamo (tutto modulo 3):

h = x2 + 2x+ 2 = 1 · h + 0 · gg = x2 + 1 = 0 · h + 1 · g

2x+ 1 = h − g2x2 + x = xh − xgx+ 1 = xh + (1 − x)g

2 = (x+ 1)h − xg1 = (2x+ 2)h + xg.

Quindi a = x, b = 2x+ 2 modulo 3. E quindi, modulo 3,

eb = (x2 + x+ 2)(2x + 2) = 2x3 + x2 + 1 = (2x+ 1)g + x = qg + r.

Allora u = r = x e

v = ea+ qh = (x2 + x+ 2)x+ (2x+ 1)(x2 + 2x+ 2) = 3x3 + 6x2 + 8x+ 2

= 2x+ 2 mod 3.

Si vede che deg(v) < deg(h) mod p ma non e detto che v abbia grado minore di h senzail modulo p.

Ora

g1 = g + 3u = x2 + 3x+ 1

h1 = h+ 3(2x+ 2) = x2 + 8x+ 8.

Abbiamof − g1h1 = −9x3 − 36x2 − 36x− 9 = 0 mod 9

quindi va bene.Abbiamo, per k = 2,

e =f − g1h1

9= −x3 − 4x2 − 4x− 1 = 2x3 + 2x2 + 2x+ 2 mod 3.


Poiche g1 = g mod p e h1 = h mod p gli a e b del passo precedente vanno ancora bene.Abbiamo

eb = x4 + 2x3 + 2x2 + 2x+ 1 = (x2 + 2x+ 1)g1 + 0 = qg + r.

Quindi u = r = 0 e

v = ea+ qh1 = (2x3 + 2x2 + 2x+ 2)x+ (x2 + 2x+ 1)(x2 + 8x+ 8)

= 2x+ 2 mod 3.

Ora

g2 = g1 + 9u = g1 = x2 + 3x+ 1

h2 = h1 + 9(2x + 2) = x2 + 26x+ 26.

Abbiamo f = g2h2 mod 27. Procedendo abbiamo

g3 = x2 + 3x+ 1

h3 = x2 + 80x+ 80.

Abbiamo f = g3h3 mod 81 e cosı via.

Adesso vediamo un modo per collegare i fattori “sollevati” con i “veri” fattori di f .

Definizione 3.4.7 Posto f =∑n

i=0 fixi ∈ C[x]. La norma di f e

||f || =

√√√√n∑

i=0

|fi|2.

Lemma 3.4.8 Sia h ∈ C[x], a ∈ C. Allora

||(x− a)h|| = |a|||(x − a−1)h||.

Dimostrazione. Poniamo h =∑m

i=0 hixi. Abbiamo

(x− a)h = hmxm+1 + (hm−1 − ahm)xm + . . . + (h0 − ah1)x− ah0

=m+1∑

i=0

(hi−1 − ahi)xi

dove definiamo h−1 = hm+1 = 0.Abbiamo in generale che

|u− v|2 = (u− v)(u − v) = uu− uv − uv + vv

= |u|2 − uv − uv + |v|2.

Abbiamo quindi

||(x− a)h||2 =m+1∑

i=0

|hi−1 − ahi|2

=∑

(|hi−1|2 − ahi−1hi − ahi−1hi + |ahi|2)

=∑

(|hi|2 − ahi−1hi − ahi−1hi + |ahi−1|2) =∑

|ahi−1 − hi|2.


Perche∑ |hi−1|2 =

∑ |hi|2 e

|ahi|2 = |a|2|hi|2 = |ahi|2.

Quindi

||(x− a)h||2 = ||(ax− 1)h||2

= |a|||(x− a−1)h||= |a|||(x− a−1)h||.

�

Teorema 3.4.9 (Landau-Mignotte) Sia f ∈ Z[x] e g ∈ Z[x] un fattore di f , deg(g) = m.Scriviamo g =

∑mi=0 gix

i. Allora

|gi| ≤(m

i

)||f ||.

Dimostrazione. Siano b1, . . . , bs e a1, . . . , at in C gli zeri di f con molteplicita (cioe unozero di molteplicita k compare k volte), e |bi| > 1 e |ai| ≤ 1.

Scriviamo f =∑n

i=0 fixi. Allora

f = fn

s∏

i=1

(x− bi)

t∏

j=1

(x− aj)

quindi, per il Lemma 3.4.8

||f || = ||fn

s∏

i=1

(x− bi)

t∏

j=1

(x− aj)|| = |a1 · · · at|||fn

t∏

j=1

(x− a−1j )

s∏

i=1

(x− bi)||.

Se h =∑

i hixi, allora ||h|| ≥ |h0| perche ||h||2 =

∑ |hi|2. Quindi

||f || ≥ |a1 · · · at||fn||a−11 · · · a−1

t ||b1 · · · bs|.

Per z ∈ C, |zz−1| = 1. Quindi

||f || ≥ |fnb1 · · · bs|.

Siano γ1, . . . , γm gli zeri di g. Allora g = gm(x− γ1) · · · (x− γm) quindi

gi = (−1)igmσm−i(γ1, . . . , γm)

dove σi(x1, . . . , xm) e l’i-esimo polinomio simmetrico elementare in x1, . . . , xm, cioe

σi(x1, . . . , xm) =∑

1≤j1<j2<...<ji≤m

xj1 · · · xji.

Si ha che σi(x1, . . . , xm) e una somma di(mi

)monomi di grado i.


Assumiamo che |γ1| ≥ |γ2| ≥ . . . ≥ |γm|. Allora

|σi(γ1, . . . , γm)| ≤(m

i

)|γ1 · · · γi|

≤(m

i

)|b1 · · · bs|

≤(m

i

) ||f |||fn|

quindi

|gi| ≤ |gm|(

m

m− i

) ||f |||fn|

= |gm|(m

i

) ||f |||fn|

.

Abbiamo |gm| ≤ |fn| perche gm divide fn, quindi

|gi| ≤(m

i

)||f ||.

�

Lemma 3.4.10 Sia g ∈ Z[x], g =∑m

i=0 gixi. Sia B > 0 con |gi| < B. Sia M un intero con

M > 2B e scriviamo g mod M =∑m

i=0 gixi dove gi ∈

(−M

2 ,M2

]. Allora

g =

m∑

i=0

gixi

quindi g = g mod M e gi = gi.

Dimostrazione. Per assurdo, sia gi 6= gi. Allora gi − gi = kM con |k| ≥ 1. Ma |gi| ≤ M2

quindi

|gi| = |kM + gi| ≥M

2> B

ma questa e una contraddizione. �

Da questi risultati segue che possiamo usare la seguente procedura per la fattorizzazionedi f in Z[x]. Prima scegliamo un primo p. Qui, per semplicita, assumiamo che f mod p e ilprodotto di al massimo due fattori irriducibili.

- Se f mod p e irriducibile allora f e irriducibile, e ci fermiamo.- Altrimenti supponiamo che f mod p = (g mod p)(h mod p), dove g mod p e h mod p in

Fp[x] sono irriducibile e diversi. (Questi si trovano con l’algoritmo di Berlekamp.)- Con il sollevamento di Hensel troviamo gk e hk tali che f = gkhk mod pk.- Con il Teorema Landau-Mignotte troviamo B per il quale tutti i coefficienti dei fattori

di f sono in valore assoluto < B.Sia M = pk0 con k0 tale che M > 2B. Abbiamo

gk0mod M =

∑gix

i, gi ∈(−M

2,M

2

]

hk0mod M =

∑hjx

j , hi ∈(−M

2,M

2

].

Allora f = gk0hk0

e la fattorizzazione di f oppure f e irriducibile.


Esempio 3.4.11 Come nell’Esempio 3.4.6, sia f = x4 + 2x3 − 3x2 − 4x + 1 quindi ||f ||2 =1 + 4 + 9 + 16 + 1 = 31. Allora α2x

2 + α1x+ α0 un fattore di f . Abbiamo

|α2| ≤(

2

2

)√31, |α1| ≤

(2

1

)√31, |α0| ≤

(2

0

)√31

quindi |αi| ≤ 2√

31, quindi |αi| ≤ 11 visto che αi ∈ Z e dunque B = 11.

Sappiamo che f = g3h3 mod 27 dove g3 = x2 + 3x+ 1 e h3 = x2 + 26x+ 26.

Scegliamo M = 27 > 2B = 22. Ora

g3 mod M = x2 + 3x+ 1

h3 mod M = x2 − x− 1

e f = (x2 + 3x+ 1)(x2 − x− 1); quindi abbiamo fattorizzato f .

3.4.2 Sollevamento di Hensel per piu fattori

Dato f ∈ Z[x] e f1, . . . , fr ∈ Z[x], p un primo con fi, fj coprimi modulo p. Sia deg(f1)+ . . .+deg(fr) = deg(f), f = f1 · · · fr mod p.

Calcoliamo f1, . . . , fr ∈ Z[x] con fi = fi mod p e f = f1 · · · fr mod pk per un certo k.

1) Sia m =⌈

r2

⌉e g = f1 · · · fm, h = fm+1 · · · fr.

2) Con il sollevamento di Hensel calcoliamo g, h ∈ Z[x] con g = g mod p, h = h mod p ef = gh mod pk.

3) Ricorsivamente calcoliamo f1, . . . , fr con fi = fi mod p, g = f1 · · · fm mod pk, h = fm+1 · · · fr modpk.

4) f = f1 · · · fr mod pk.

Algoritmo

Vediamo la procedura per fattorizzare f ∈ Z[x] libero di quadrati.

1) Si sceglie un primo p tale che f mod p e libero di quadrati (e p non divide il coefficientedi testa di f).

2) Con Landau-Mignotte calcoliamo B tale che

|coefficiente di un fattore di f | ≤ B

e scegliamo k tale che M = pk > 2B.

3) Siano f1, . . . , fr i fattori irriducibili di f mod p (ottenuti con l’algoritmo di Berlekamp).

4) Con il sollevamento di Hensel troviamo f1, . . . , fr ∈ Z[x] tale che f = f1 · · · fr mod pk efi = fi mod p.

3.5 Esercizi 57

5) Per ogni S ⊂ {1, . . . , r} calcoliamo

gS =∏

i∈S

fi e hS =∏

i6∈S

fi.

Scriviamo i coefficienti di gS e hS modulo M in(−M

2 ,M2

].

Se f = gShS abbiamo trovato una fattorizzazione. Se, per ogni S, fS 6= gShS allora f eirriducibile.

3.5 Esercizi

1. Provare che x4 + x+ 1 ∈ F2[x] e irriducibile.

2. Fattorizzare x7 + 1 ∈ F2[x] e x4 + x+ 1 ∈ F3[x].

3. Sia f = x4 + 5x3 + 6x2 − x− 1 e g = x2 + 1, h = x2 + 2x+ 2. Allora g mod 3 e h mod 3sono irriducibili (in F3[x]) e f = gh mod 3. Siano gk, hk i polinomi ottenuti mediante ilsollevamento di Hensel. (Quindi f = gkhk mod 3k.)

(a) Calcolare gk, hk per k = 2, 3.

(b) Provare che gk = x2 + 3x+ 1 e hk = x2 + 2x+ 3k − 1 per k ≥ 2.

(c) E’ dato che i coefficienti di un fattore di f sono ≤ 48 in valore assoluto. Fattorizzaref .

4. Sia f = x5+2x3+2x2+x+1. Fattorizzare f mod 3, e provare che f ∈ Q[x] e irriducibile.

5. In questo esercizio proviamo che f = x4 + 1 ∈ Q[x] e irriducibile, ma che f mod pfattorizza per ogni primo p.

(a) Fattorizzare f mod 2 (suggerimento: e facile trovare una radice di f).

(b) Sia p un primo dispari. Sia V lo spazio dei v ∈ Fp[x]/〈f〉 tali che vp = v mod f .Calcolare una base di V , trattando i casi p = 1 + 4k, k pari e dispari e p = 3 + 4k,k pari e dispari separatemente. Concludere che f mod p fattorizza per ogni primop.

(c) Fattorizzare f mod 5.

(d) Mediante il sollevamento di Hensel trovare g, h ∈ Z[x] con f = gh mod 125.

(e) Trovare un limite sui coefficienti di un possibile divisore di f in Z[x] (Landau-Mignotte). Provare che f e irriducibile.

Algebra Computazionale - UniTrentodegraaf/compalg/alg_comp.pdf · 1.1.4 Algoritmo di divisione con...

Documents

Transcript of Algebra Computazionale - UniTrentodegraaf/compalg/alg_comp.pdf · 1.1.4 Algoritmo di divisione con...