Maria De Falco » 7.Richiami sui campi finiti. Generalità sulle curve ellittiche

Un campo di ordine 9

Esempio di costruzione di un modello di un campo finito
Si consideri l’anello Z₃ [x] dei polinomi a coefficienti in Z₃ nell’indeterminata x.
Si consideri f(x)=x²+[1]₃ appartenente a Z₃ [x] e sia I l’ideale generato da f(x).
f(x) non ha radici in Z_{3  ⇒}  f(x) è irriducibile su Z₃ ⇒  I è un ideale massimale
⇒ l’anello quoziente F=Z₃ [x] /I è un campo.
Ovviamente 0_F=I e 1_F= [1]₃ +I ; inoltre:
F={g(x)+I  |  g(x)є Z₃ [x]} = {([a₀ ]₃+[a₁ ]₃ x)+I  |  a₀ , a₁ є{0,1,2}}. In particolare, |F|=9.
Si fornirà ora del campo F, appena costruito, una descrizione astratta in cui non si fa più riferimento a Z_3.

Un campo di ordine 9

Siano a₀ , a₁ є{0,1,2}; allora ([a₀ ]₃+[a₁ ]₃ x)+I = ([a₀ ]₃+I) + ([a₁ ]₃ x+I) = (a₀ [1]₃+I) + (a₁[1]₃ x+I) =
= a₀ ( [1]₃+I) + a₁ ( x+I) = a₀ 1_F + a₁ ( x+I) .
Quindi F={a₀ 1_F + a₁ ( x+I)  |  a₀ , a₁ є{0,1,2}}.
Si ponga β=x+I ⇒  l’elemento β ha la seguente proprietà:
β²+1_F = (x+I)²+1_F = (x²+I)+([1]₃+I) = (x²+[1]₃)+I = I =0_F ⇒ β²=-1_F
Si ha dunque F ={ a₀1_F+a₁β  |    a₀ , a₁ є{0,1,2}}, dove β è un elemento di periodo 4 di F*=(F\{0_F } , ∙) .
Si calcolerà ora il periodo di 1_F+β nel gruppo moltiplicativo (F\{0_F } , ∙), dove F è il campo su costruito.
Poiché |F\{0_F }|=8, il periodo di 1_F+β è 2 oppure 4 oppure 8.
(1_F+β)²=1_F+2β+β² = 2β ; quindi (1_F+β)⁴ = 4β² = -4∙1_F
Quindi il periodo di  il periodo di 1_F+β è 8, cioè 1_F+β è un generatore di (F\{0_F } , ∙).

Caratteristica di un anello unitario

I concetti presentati nelle prossime due slide fanno parte dei contenuti dei corsi di Algebra del primo anno, ma vengono esplicitamente richiamati, in quanto verranno più volte utilizzati nel seguito.
Sia A un anello unitario.
Si consideri la funzione f: Z → A definita ponendo f(n)=n∙1_A .
Si dimostra facilmente che f è un omomorfismo di anelli
⇒ esiste un unico c≥0 tale che ker f = cZ. Segue allora dal Teorema di Omomorfismo (per gli anelli) che:
(1) f(A)= {n∙1_A   |  nєZ} è un sottoanello di A
(2) f(A) è isomorfo all’anello  Z_c
(3) in particolare, se c=0, f è un monomorfismo, e f(A) è isomorfo Z
(4) se c>0,c è il minimo intero postivo tale che c∙1_A =0_A (cioè c è l’ordine del sottogruppo <1_A > di (F,+)
(5) se c>0, c è il minimo intero postivo tale che c∙a=0_A  per ogni elemento a di A
(6) Il numero c si chiama caratteristica di A, e si indica con il simbolo char(A)
(7) Il sottoanello f(A) di A si chiama sottoanello fondamentale di A e si indica con il simbolo E(A)

Caratteristica di un anello unitario

Proposizione 7.1
Sia F un campo. Allora  char(F) è 0 oppure è un numero primo.
Dimostrazione
Sia c=char(F) e si supponga che sia c≠0. Siano c₁ e c₂ numeri interi positivi tali che c=c₁c₂
⇒ 0_F= c∙1_F = (c₁∙1_F)(c₂∙1_F) ⇒  esiste iє{1,2} tale che (c_i∙1_F)=0_F ⇒  c_i=c perché c è il minimo intero positivo tale che  c∙1_F =0_F . Quindi c è primo.

Sottocampo minimo di un campo

Proposizione 7.2
Sia F un campo, e sia ={ab^-1 |  aєE(F)  ,  bєE(F)\{0_F}}.
Allora coincide con l’intersezione di tutti i sottocampi di F e
(i) se char(F)=0, allora E(F) è isomorfo all’anello Z e è isomorfo al campo razionale
(ii) se char(F)=p≠0, allora =E(F)≈Z_p
Dimostrazione
Se K è un qualunque sottocampo di F, 1_F appartiene a K, sicché K contiene E(F) e quindi contiene .
Inoltre il sottoanello E(F) è un dominio di integrità, sicché è un sottocampo di F isomorfo al campo dei quozienti del dominio di integrità E(F): da questa osservazione seguono la (i) e la (ii) (cfr. S. Franciosi, F. de Giovanni “Elementi di Algebra”, Lemma 5.8.2).
Sia F un campo. Il sottocampo si chiama sottocampo minimo di F.
Nel seguito, dato un campo F, per ogni numero intero n, l’elemento n∙1_F verrà indicato soltanto con n (in particolare il simbolo 1 indicherà anche 1_F , e il simbolo 0 indicherà anche 0_F ). Quindi:

1. E(F) ={r  |  rєZ};
2. se char(F)=p>0 e r,s sono numeri interi, allora r=s in F se e solo se r≡s (mod p).

Richiami sui campi finiti

Sia F un campo finito; segue dalla Proposizione 8.10, che il gruppo moltiplicativo F *=(F\{0},∙) è ciclico di ordine |F|-1.
La prossima proposizione fornisce informazioni sulla struttura del gruppo additivo (F,+).
Proposizione 7.3
Sia F un campo finito.
Allora |F|=pⁿ, dove p e n sono, rispettivamente, la caratteristica di F e il grado di F su . Inoltre:

1. (F,+)=(E₁,+)⊕…⊕(E_n ,+), dove ciascun (E_i ,+) è un gruppo abeliano di ordine p
2. per ogni elemento a appartenente a F\{0}, il periodo di a nel gruppo (F,+) è p

Dimostrazione
p=char(F)  ⇒  =E(F)≈Z_p
Dal fatto che F è un  - spazio vettoriale di dimensione n, segue allora l’affermazione (1) (cfr S. Franciosi, F. de Giovanni “Elementi di Algebra”, Teorema 6.4.5), e da essa segue che |F|=pⁿ e che ogni elemento di F\{0} ha periodo p nel gruppo (F,+).

Richiami sui campi finiti

Proposizione 7.4  (senza dimostrazione)
Siano p un numero primo positivo e n un numero naturale positivo. Allora

1. esiste un campo F tale che |F|=pⁿ ;
2. due campi di ordine pⁿ sono isomorfi.

Costruzione di un campo di ordine pⁿ

Sia p un numero primo positivo e sia n un numero naturale positivo.
Si è detto che, a meno di isomorfismi, esiste un unico campo di ordine pⁿ.
Esistono però diversi procedimenti per costruire campi di un fissato ordine. Si illustrerà ora una costruzione di un campo di ordine pⁿ che sarà utile per calcolare la complessità dell’esecuzione di operazioni in un campo finito.
Si consideri l’anello Z_p[x] dei polinomi a coefficienti in Z_p nell’indeterminata x.
Sia f(x) un polinomio appartenente Z_p[x] irriducibile su Z_p e sia I l’ideale generato da f(x)
⇒  I è un ideale massimale ⇒ l’anello quoziente F=Z_p[x] è un campo.
Ovviamente 0_F=I e 1_F= [1]₃ +I .
Se g(x) è un qualunque elemento di Z_p[x], allora, per l’Algoritmo della Divisione Euclidea tra polinomi, si ha che esistono polinomi q(x) e r(x) tali che g(x)=f(x)q(x)+r(x) con r(x)=[0]_p oppure gr(r(x))<n; dunque:
F={g(x)+I  |  g(x)єZ_p[x]} = {r(x) +I  |  r(x)=[0]_p oppure gr(r(x))<n}   ⇒
F= { ([a₀]_p +[a₁]_p x+ … + [a_n-1]_p x^n-1 )+I  |  a_i є{ 0,…,p-1} }.
Quindi |F|=pⁿ .

Prime definizioni sulle curve ellittiche

Definizione 7.5
Sia F un campo e si consideri l’equazione f(x,y)=0 , a coefficienti in F, nelle incognite x,y, definita nel seguente modo:
(i) se char(F)≠2,3, allora f(x,y)=0 è l’equazione y²=x³+ax+b
(ii) se char(F)=2, allora f(x,y)=0 è l’equazione y²+cy=x³+ax+b oppure y²+xy=x³+ax²+b
(iii) se char(F)=3, allora f(x,y)=0 è l’equazione y²=x³+ax²+bx+c
con la condizione che il polinomio appartenente a F[x] presente al secondo membro dell’equazione sia privo di radici multiple in un campo di spezzamento su F.
Si chiama curva ellittica su F l’insieme E={(u,v)є F² | f(u,v)=0}U{Ω}, dove Ω è un ente non appartenente a F², che viene detto punto all’infinito di E.

Prime definizioni sulle curve ellittiche

Definizione 7.6
Sia F un campo e sia E una curva ellittica su F
Si definisce un’operazione + in E ponendo:

1. P+Ω=P  per ogni P appartenente ad E

2. (x_P ,y_P)+(x_P , – y_P) = Ω p er ogni (x_P , y_P) appartenente a E\{Ω}

3. (x_P ,y_P)+(x_P ,y_P)= (dove )  per ogni (x_P , y_P) appartenente a E\{Ω} tale che y_P≠-y_P (questo caso non si presenta se char(F)=2)

4. (x_P , y_P)+(x_Q , y_Q)= con

per ogni (x_P , y_P) e (x_Q , y_Q) appartenenti a E\{Ω} tali che x_P≠x_Q

Per un approfondimento, si veda il file Koblitz_CurveEllittiche.

Prime proprietà delle curve ellittiche

Proposizione 7.7  (senza dimostrazione)
Sia F un campo e sia E una curva ellittica su F. Allora l’operazione + introdotta con la Definizione 7.6 è tale che (E,+) è un gruppo abeliano.
Se E è una curva ellittica, il punto all’infinito di E, che è l’elemento neutro del gruppo (E,+), verrà nel seguito indicato con 0_E , o anche solo con 0.
Definizione 7.8 
Sia F un campo. Si chiama carattere quadratico di F la funzione χ:F→{-1,0,1} definita ponendo
Χ(0)=0
χ(u)=1 se u è un quadrato in F*
χ(u)=-1 se u è un elemento di F* che non è un quadrato

Prime proprietà delle curve ellittiche

Sia F un campo di caratteristica diversa da 2. Allora è facile verificare che per ogni elemento u di F, il numero di radici dell’equazione y²=u è 1+χ(u).
Sia E una curva ellittica su un campo finito F di ordine q.

1. Se char(F)≠2, allora

,

dove y²=f(x) è l’equazione di E.

2. (TEOREMA DI HASSE) 

3. Esistono, per molti valori di q (anche molto alti), algoritmi che permettono di calcolare l’ordine di E in un tempo polinomiale rispetto all’input q. Il primo è stato l’algoritmo di Schoof (R. Schoof: “Elliptic curves over finite fields and the computation of square roots modulo p”, Math. Comp. 44 (1985), 483–494).

Discriminante e radici multiple di un polinomio

Discriminante e esistenza di radici multiple di un polinomio (cfr. “Codici correttori: Un’introduzione” di Luca Giuzzi, Springer)
Definizione 7.9
Sia F un campo, sia f(x) un polinomio appartenente a F[x] di grado n≥2, e sia K un campo di spezzamento di f(x) su F.
Si ponga f(x)=a₀+a₁x+…+a_nxⁿ  con a₀ , … ,a_n є F; in K[x] sia f(x)=a_n(x-β₁ )…(x-β_n ) con β₁ ,… ,β_n radici di f(x).
Sia

;

Δf si chiama discriminante di f(x).

Da tale definizione segue che
f(x) è privo di radici multiple in K se e solo se Δf≠0

Discriminante e radici multiple di un polinomio

Discriminante e esistenza di radici multiple di un polinomio (cfr. “Codici correttori: Un’introduzione” di Luca Giuzzi, Springe
Definizione 7.10 
Sia F un campo, e siano  g(x), h(x)  polinomi appartenenti a F[x] di grado ≥1.
Si ponga g(x)=b₀+b₁x+…+b_nxⁿ  e h(x)=c₀+c₁x+…+c_mx^m  con b₀ , … ,b_n ,c₀ , … ,c_m є F, b_n≠0, c_m≠0.
Si chiama risultante di g(x) e h(x), e si indica con R(g(x),h(x)), il determinante della matrice quadrata di ordine m+n

Discriminante e radici multiple di un polinomio

Proposizione 9.11 (senza dimostrazione)
Sia F un campo, sia f(x) un polinomio non nullo appartenente a F[x] tale che il polinomio derivato Df(x) abbia grado almeno 1 (sicché il grado n di f(x) è grado almeno 2). Sia a_n il parametro direttore di f(x). Allora Δf=.
La proposizione appena enunciata garantisce che Δf è un elemento di F e può essere espresso in funzione dei soli coefficienti di f(x).
Sia F un campo di caratteristica diversa da 2 e da 3, siano a,b elementi di F, e si consideri l’equazione y^2=x³+ax+b (nelle incognite x e y). Tale equazione rappresenta una curva ellittica su F se e solo se il polinomio f(x)=x³+ax+b è privo di radici multiple in un suo campo di spezzamento su F, cioè se e solo se il discriminante Δf≠0.
Si ha Df(x)=3x²+a  ⇒  R(f(x),Df(x))=-det A con

Quindi il polinomio x³+ax+b è privo di radici multiple in un suo campo di spezzamento su F se e solo se 4a³+27b²≠0.