Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 Z3 [x] dei polinomi a coefficienti in Z3 nell’indeterminata x.
Si consideri f(x)=x2+[1]3 appartenente a Z3 [x] e sia I l’ideale generato da f(x).
f(x) non ha radici in Z3  ⇒  f(x) è irriducibile su Z3 ⇒  I è un ideale massimale
⇒ l’anello quoziente F=Z3 [x] /I è un campo.
Ovviamente 0F=I e 1F= [1]3 +I ; inoltre:
F={g(x)+I  |  g(x)є Z3 [x]} = {([a0 ]3+[a1 ]3 x)+I  |  a0 , a1 є{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 Z3.

Un campo di ordine 9

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

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∙1A .
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∙1A   |  nєZ} è un sottoanello di A
(2) f(A) è isomorfo all’anello  Zc
(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∙1A =0A (cioè c è l’ordine del sottogruppo <1A > di (F,+)
(5) se c>0, c è il minimo intero postivo tale che c∙a=0A  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 c1 e c2 numeri interi positivi tali che c=c1c2
⇒ 0F= c∙1F = (c1∙1F)(c2∙1F) ⇒  esiste iє{1,2} tale che (ci∙1F)=0F ⇒  ci=c perché c è il minimo intero positivo tale che  c∙1F =0F . Quindi c è primo.

Sottocampo minimo di un campo

Proposizione 7.2
Sia F un campo, e sia \bar E (F)={ab-1 |  aєE(F)  ,  bєE(F)\{0F}}.
Allora \bar E(F) coincide con l’intersezione di tutti i sottocampi di F e
(i) se char(F)=0, allora E(F) è isomorfo all’anello Z e \bar E(F) è isomorfo al campo razionale
(ii) se char(F)=p≠0, allora \bar E(F)=E(F)≈Zp
Dimostrazione
Se K è un qualunque sottocampo di F, 1F appartiene a K, sicché K contiene E(F) e quindi contiene \bar E(F).
Inoltre il sottoanello E(F) è un dominio di integrità, sicché \bar E(F) è 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 \bar E (F) si chiama sottocampo minimo di F.
Nel seguito, dato un campo F, per ogni numero intero n, l’elemento n∙1F verrà indicato soltanto con n (in particolare il simbolo 1 indicherà anche 1F , e il simbolo 0 indicherà anche 0F ). 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|=pn, dove p e n sono, rispettivamente, la caratteristica di F e il grado di F su \bar E(F). Inoltre:

  1. (F,+)=(E1,+)⊕…⊕(En ,+), dove ciascun (Ei ,+) è 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)  ⇒  \bar E(F)=E(F)≈Zp
Dal fatto che F è un \bar E(F) - 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|=pn 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|=pn ;
  2. due campi di ordine pn sono isomorfi.

Costruzione di un campo di ordine pn

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 pn.
Esistono però diversi procedimenti per costruire campi di un fissato ordine. Si illustrerà ora una costruzione di un campo di ordine pn che sarà utile per calcolare la complessità dell’esecuzione di operazioni in un campo finito.
Si consideri l’anello Zp[x] dei polinomi a coefficienti in Zp nell’indeterminata x.
Sia f(x) un polinomio appartenente Zp[x] irriducibile su Zp e sia I l’ideale generato da f(x)
⇒  I è un ideale massimale ⇒ l’anello quoziente F=Zp[x] è un campo.
Ovviamente 0F=I e 1F= [1]3 +I .
Se g(x) è un qualunque elemento di Zp[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(xZp[x]} = {r(x) +I  |  r(x)=[0]p oppure gr(r(x))<n}   ⇒
F= { ([a0]p +[a1]p x+ … + [an-1]p xn-1 )+I  |  ai є{ 0,…,p-1} }.
Quindi |F|=pn .

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 y2=x3+ax+b
(ii) se char(F)=2, allora f(x,y)=0 è l’equazione y2+cy=x3+ax+b oppure y2+xy=x3+ax2+b
(iii) se char(F)=3, allora f(x,y)=0 è l’equazione y2=x3+ax2+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)є F2 | f(u,v)=0}U{Ω}, dove Ω è un ente non appartenente a F2, 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. (xP ,yP)+(xP , – yP) = Ω p er ogni (xP , yP) appartenente a E\{Ω}

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

4. (xP , yP)+(xQ , yQ)=((\frac{y_Q-y_P}{x_Q-x_P})^2-x_P-x_Q,-y_P+\frac{y_Q-y_P}{x_Q-x_P}(x_P-\bar x)) con \bar x=(\frac{y_Q-y_P}{x_Q-x_P})^2-x_P-x_Q

 

per ogni (xP , yP) e (xQ , yQ) appartenenti a E\{Ω} tali che xP≠xQ

 

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 0E , 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 y2=u è 1+χ(u).
Sia E una curva ellittica su un campo finito F di ordine q.

1. Se char(F)≠2, allora

|E|=1+ \sum _{u\in F} (1+ \chi (f(u)))=q+1 + \sum _{u\in F} \chi (f(u)),

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

2. (TEOREMA DI HASSE) ||E|-(q+1)|\leq 2 \sqrt q

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)=a0+a1x+…+anxn  con a0 , … ,an є F; in K[x] sia f(x)=an(x-β1 )…(x-βn ) con β1 ,… ,βn radici di f(x).
Sia

\Delta f=a_n^{2n-2}\prod _{1\leq i <j\leq n} (\beta _i - \beta _j);

Δ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)=b0+b1x+…+bnxn  e h(x)=c0+c1x+…+cmxm  con b0 , … ,bn ,c0 , … ,cm є F, bn≠0, cm≠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
\left(\begin{array}{l}b_n\hspace{0.5cm} ... \hspace{0.5cm} b_0 \hspace{0.5cm} 0 \hspace{0.5cm} ... \hspace{0.5cm} 0 \\ 0\hspace{0.5cm}  b_n\hspace{0.5cm}  ... \hspace{0.5cm} b_0\hspace{0.5cm}  0 \hspace{0.5cm} ... \hspace{0.5cm} 0 \\ ... \\ 0\hspace{0.5cm}  ... \hspace{0.5cm} 0 \hspace{0.5cm} b_n\hspace{0.5cm}  ... \hspace{0.5cm} b_0 \\ c_m \hspace{0.5cm} ... \hspace{0.5cm} c_0\hspace{0.5cm}  0\hspace{0.5cm}  ...\hspace{0.5cm}  0 \\ 0 \hspace{0.5cm} c_m\hspace{0.5cm}  ...\hspace{0.5cm}  c_0\hspace{0.5cm}  0\hspace{0.5cm}  ... \hspace{0.5cm} 0 \\ ... \\ 0\hspace{0.5cm}  ... \hspace{0.5cm} 0 \hspace{0.5cm} c_m \hspace{0.5cm} ... \hspace{0.5cm} c_0\end{array}\right)

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 an il parametro direttore di f(x). Allora Δf=\; (-1)^{\frac{n(n-1)}{2}}a_n^{-1}R(f(x),Df(x)).
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=x3+ax+b (nelle incognite x e y). Tale equazione rappresenta una curva ellittica su F se e solo se il polinomio f(x)=x3+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)=3x2+a  ⇒  R(f(x),Df(x))=-det A con
A=\left(\begin{array}{l}1\hspace{0.5cm} 0\hspace{0.5cm} a\hspace{0.5cm} b\hspace{0.5cm} 0 \\ 0\hspace{0.5cm} 1\hspace{0.5cm} 0\hspace{0.5cm} a\hspace{0.5cm} b \\ 3\hspace{0.5cm} 0\hspace{0.5cm} a\hspace{0.5cm} 0\hspace{0.5cm} 0 \\ 0\hspace{0.5cm} 3\hspace{0.5cm} 0\hspace{0.5cm} a\hspace{0.5cm} 0 \\ 0\hspace{0.5cm} 0 \hspace{0.5cm}3\hspace{0.5cm} 0\hspace{0.5cm} a \end{array}\right)
Quindi il polinomio x3+ax+b è privo di radici multiple in un suo campo di spezzamento su F se e solo se 4a3+27b2≠0.

I materiali di supporto della lezione

S. Franciosi, F. de Giovanni “Elementi di Algebra”, Lemma 5.8.2

S. Franciosi, F. de Giovanni “Elementi di Algebra”, Teorema 6.4.5

R. Schoof: “Elliptic curves over finite fields and the computation of square roots modulo p”, Math. Comp. 44 (1985), 483--494

“Codici correttori: Un'introduzione” di Luca Giuzzi, Springer

Curve Ellittiche

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion