Universit a tea Politehnic dinBucure³ti [615894]

Universit a tea Politehnic  dinBucure³ti
F a cul t a tea de “ti inµe Aplica te
CURBE ELIPTICE PESTE CORPURIFINITE
Coordona tor ³ti inµific,
Conf. dr. Emil Simion
Masterand: [anonimizat]-V er onic a Chir ob o c e a
2017
BUCURE“TI

1 Preliminarii
1.1 Notaµii
Fp – corpul cu p elemen te, unde p este n um r natural prim;
E(Fp) – curba eliptic  p este corpul Fp sub forma W eierstrass;
Fp[X] – inelul de p olinome în tr-o nedeterminat  cu co ecienµi în corpul Fp ;
1.2 Deniµii, T eoreme
Deniµie (Grup) :
FieG o m ulµime nevid  ³i "" o op eraµie algebric  p e G ::GG!G .
Not m(x;y) =xy .(G;) se n ume³te grup dac :
1)"" este lege in tern  p e G :8x;y2G)xy2G ;
2)"" este aso ciativ  :8x;y;z2G:x(yz) = (xy)z ;
3)"" admite elemen t neutru: 9e2G:8x2G xe=ex=x ;
4) orice elemen t din G e in v ersabil:8x2G9x12G:
xx1=x1x=e:
Dac  este com utativ   (i.e. 8x;y2G; xy=yx ) atunciG se n ume³te
grup com utativ sau ab elian.
T eorema de clasicare a grupurilor ab eliene nite :
Fie(G;
) un grup ab elian nit cu card(G) =n ; atunciG'Zd1:::Zds ,
unde 1<d 1; d1j:::jds (divizibilitatea are lo c în N ) ,d1
:::
ds=n .
Deniµie (Subgrup) :
Fie(G;) grup ³iH o subm ulµime nevid  a lui G ;H se n ume³te subgrup
inG dac :
1)"" e lege in tern  în H ;
2)(H;) este grup.
Notaµie:HG .
Deniµie (Subgrup generat de o m ulµime) :
Fie(G;) grup ³iM o subm ulµime nevid  a lui G ; se n ume³te subgrupul
generat de m ulµimea M , notat<M > , m ulµimea
fg2G:g=x1x2:::xn , unden0 ,xi2M saux1
i2M;i = 1;:::;ng .
1

În particular, dac  m ulµimea M este format  din tr-un singur elemen t,
M=fxg , se n ume³te subgrupul generat de un elemen t
<x> =fg2G:g=x1x2:::xn , unden0 ,xi=x sauxi=x1;
i= 1;:::;ng .
Observ aµie :
(<M >;) este grup.
Deniµie (Ordin ul un ui elemen t) :
Fie(G;) grup ³ix2G ; se n ume³te ordin ul lui x , notat cuord(x) , car-
dinalul subgrupului generat de x înG .
T eorema lui Lagrange :
Fie(G;) grup nit cu card(G) =n ³iH subgrup în G ; atunci:
1)card(H)jcard(G) ;
2)ord(x)jcard(G)8x2G .
Deniµie (Grup ciclic) :
Un grupG se n ume³te grup ciclic dac  exist  un elemen t a2G:
<a> =G .
Deniµie (Morsm de grupuri) :
Fie(G1;) ³i(G2;) grupuri; o funcµie f:G1!G2 se n ume³te morsm
de grupuri dac  f(xy) =f(x)f(y)8x;y2G1 .
Deniµie (Izomorsm de grupuri) :
Fie(A;);(B;) dou  grupuri; un morsm de grupuri se n ume³te izomor-
sm dac  e funcµie bijectiv  .
T eorem  :
Fie(G1;) ³i(G2;) grupuri nite, f:G1!G2 o funcµie; urm toarele
armaµii sun t ec hiv alen te:
1.f este injectiv  
2.f este surjectiv  
3.f este bijectiv  
Observ aµie :
2

În particular, daca f este un morsm injectiv de grupuri atunci f este
izomorsm de grupuri.
Deniµie (Nucleul un ui morsm) :
Fie(G1;);(G2;) grupuri ³i funcµia f:G1!G2 un morsm de gru-
puri; se n ume³te n ucleul lui f , notat cuKer(f) , m ulµimea
fx2G1:f(x) =e2g:
(Am notat cu e2 elemen tul neutru din grupul G2 .)
Deniµie (Inel) :
FieA o m ulµime nevid  înzestrat  cu dou  legi de comp oziµie, notate cu
" + " ³i"
" ;(A;+;
) se n ume³te inel dac :
1)(A;+) este grup com utativ;
2)"
" este aso ciativ  :8x;y;z2A:x
(y
z) = (x
y)
z ;
3)"
" este distributiv   faµ  de "+" :8x;y;z2A:x
(y+z) =x
y+x
z .
Dac  "
" este com utativ   (i.e. 8x;y2A:x
y=y
x ) atunciA este inel
com utativ.
Dac  "
" admite elemen t neutru atunci A este inel unitar.
Notaµii:
0 elemen tul neutru la " + " ;
1 elemen tul neutru la "
" (p e care îl v om n umi elemen tul unitate al
inelului).
Deniµie (Elemen t in v ersabil) :
Fie(A;+;
) un inel unitar; un elemen t x dinA se n ume³te elemen t in-
v ersabil dac :9y2A:y
x=x
y= 1 ;
Notaµie:U(A) =fx2A:x este elemen t in v ersabil}
Deniµie (Corp) :
Fie(A;+;
) inel unitar; A se n ume³te corp dac  U(A) =Anf0g .
Am notat cu 1A elemen tul unitate al inelului A ³i cu 1B elemen tul unitate
al ineluluiB .
Deniµie (Caracteristica un ui corp) :
Fie(K;+;
) un corp;
1) Dac n
1K6= 0K8n2Znf0g atunci denim caracteristica corpului
K , notat  cu char(K) , ca ind 0 ;
3

2) Dac 9n2Nnf0g:n
1K= 0 , ep cel mai mic n um r natural cu
aceast  proprietate, atunci denim caracteristica lui K ca indp .
Observ aµie :
Caracteristica un ui corp este sau 0 saup , undep este un n um r natural
prim.
T eorema lui F rob enius :
FieK corp com utativ cu char(K) =p ; atunci (x+y)p=xp+yp8x;y2K .
Observ aµie :
FieK corp com uativ cu char(K) =p ; atunciK conµine corpul cu p ele-
men te Fp .
Deniµie (Extindere de corpuri) :
Fie(E;+;
) ,(K;+;
) corpuri;E se n ume³te extindere a lui K dac  exist 
un morsm nen ul în tre ele. Un morsm de corpuri nen ul este injectiv, deci
v om iden tica corpul K cu un sub corp în E .
În particular, dac  K este sub corp în E atunciKE este extindere de
corpuri.
Deniµie (Elemen t algebric) :
FieKE o extindere de corpuri com utativ e; un elemen t x dinE se
n ume³te algebric p este K dac 9g2K[X] :g6= 0;g(x) = 0 .
Deniµie (Extindere algebric ) :
FieKE o extindere de corpuri com utativ e; extinderea se n ume³te
algebric  dac  orice elemen t din E este algebric p este K .
Deniµie (Corp algebric înc his) :
CorpulK se n ume³te corp algebric înc his dac  este corp com utativ ³i orice
p olinomf2K[X];grad (f) =n >0 aren r d cini (n u neap rat distincte)
înK .
Deniµie (Înc hidere algebric ) :
FieK corp com utativ; se n ume³te înc hiderea algebric  a lui K un corp
L cu urm toarele propriet µi:
1)KL este extindere algebric ;
4

2)L este corp algebric înc his.
T eorem  :
Orice corp com utativ K admite o înc hidere algebric  L , adic  p en tru orice
p olinomf2K[X] ecuaµiaf(X) = 0 are toate r d cinile în L .
Deniµii (R d cin  m ultipl , r d cin  simpl ) :
FieK corp com utativ, L înc hiderea algebric  a lui K ,f2K[X];
grad(f)1 ³i2L o r d cin  a lui f ; se n ume³te r d cin  m ultipl 
dac 9s2 : (X)sjf . În caz con trar,  se n ume³te r d cin  simpl .
Deniµie (Deriv ata formal ) :
CumK[X] este spaµiu v ectorial p este corpul K putem deni aplicaµia
liniar d:K[X]!K[X] astfel:
1)d(Xi) =i
Xi18i1;
2)d(1) = 0 .
Notaµie:d(f) =f0.
Observ aµie :
FieK corp com utativ, L înc hiderea algebric  a lui K ,f2K[X];
grad(f)1 ³i2L o r d cin  a lui f ; atunci este r d cin  m ultipl 
dac  ³i n umai dac  f() =f0() = 0 .
Deniµie (Curb  eliptic )
FieK corp com utativ, f(X) =X3+a
X+b2K[X] un p olinom. Not m
cuO punctul de la innit. V om deni noµiunea de curb  eliptic  p este corpul
K în urm toarele mo duri în funcµie de caracteristica corpului:
P en tru caracteristic  2 m ulµimea
E(K) =f(x;y)2K2:y2+y=f(x)g[fOg
se n ume³te curb  eliptic  p este corpul K ;
P en tru caracteristic  3 m ulµimea
E(K) =f(x;y)2K2:y2=X3+a
X2+b
X+cg[fOg
se n ume³te curb  eliptic  p este corpul K ;
P en tru caracteristic  diferit  de 2 ³i3 m ulµimea
E(K) =f(x;y)2K2:y2=f(x)g[fOg
5

se n ume³te curb  eliptic  p este corpul K ;
Menµion m c  în ultimele dou  cazuri p olinom ul cubic trebuie s  n u aib 
r d cini m ultiple. De asemenea deniµia este dat  p en tru curb e eliptice sub
forma W eierstrass.
Observ aµie :
FieK un corp com utativ, f2K[X] un p olinom; atunci f n u are r d –
cini m ultiple dac  ³i n umai dac  discriminan tul p olinom ului este diferit de
elemen tul zero al corpului K . Dac  p olinom ul f este de forma X3+a
X+b
atunci discriminan tul p olinom ului este 4
a327
b2.
T eorema Hasse :
Fiep un n um r prim ³i E curb  eliptic  p este corpul Fp . A tunci:
jp+ 1card(E(Fp))j<2
pp:
6

2 Capitolul 1
Studiul curb elor eliptice în domeniile: algebr , geometrie algebric , teoria
n umerelor a început la jum tatea secolului al XIX-lea.
V om prezen ta în con tin uare imp ortanµa curb elor eliptice în rezolv area
unor probleme div erse din matematic .
1. Problema n umerelor congruen te
Problema n umerelor congruen te a ap rut in secolul X, în tr-un man uscris
arab, în care s-a pus urm toarea problem : Fie n n um r în treg p ozitiv, s 
se g seasc  a un n um r raµional p ozitiv astfel încât a2+n ³ia2n s  e
p tratele unor n umere raµionale.
Deniµie : Un n um r în treg se n ume³te conguen t dac  exist  a2Qf0g
astfel încât a2+n ³ia2n s  e p tratele unor n umere raµionale.
Ulterior aceast  problem  s-a demonstrat a  ec hiv alen t  cu urm toarea: Fie
n n um r în treg p ozitiv, S  se gaseasc  tripletul de n umere raµionale p ozitiv e
(a;b;c ) astfel încât a;b;c p ot  lungimile laturilor un ui triunghi dreptunghic
de arien .
Exemple :
1.5 este n um r congruen t deoarece este aria triunghiului dreptunghic
format de laturile de lungimi20
3;3
2;41
6.
2.1 n u este n um r congruen t (demonstrat de F ermat).
Probleme desc hise:
1. G sirea un ui criteriu prin care s  se determine când un n um r este
congruen t.
2. Dat ind un n um r congruen t n s  se gaseasc  cu a jutorul un ui algo-
ritm lungimile laturilor triunghilui dreptunghic de arie n .
Leg tura curb elor eliptice cu n umerele congruen te
Problema n umerelor congruen te este ec hiv alen t  cu urm toarea problem 
din teoria curb elor eliptice:
Fien un n um r în treg p ozitiv; s  se g seasc  un punct raµonal p e curba
eliptic y2=x3n2
x p en truy diferit de 0 .
7

Cu a jutorul curb elor eliptice au fost en unµate câtev a rezultate prin care se
p oate decide dac  an umite n umere sun t congruen te sau n u, îns  problema
r mâne desc his .
2. Demonstraµia marii teoreme a lui F ermat
Marea teorem  a lui F ermat a fost en unµat  de Pierre de F ermat în an ul
1637 p e marginea unei copii a "Arithmetica", unde se menµiona c  demon-
straµia acestui fapt este prea mare p en tru a  scris  p e acea margine.
Marea teorem  a lui F ermat :
Fiea;b;c2Zf0g;n2Z;n > 2 atunci ecuaµia an+bn=cnn u are
soluµii.
În an ul 1995 matematician ul englez Andrew John Wiles public  o demon-
straµie a urm torului fapt: T oate curb ele eliptice semistabile p este m ulµimea
n umerelor raµionale sun t mo dulare. Marea teorem  a lui F ermat urmeaz  ca
un corolar a v ând în v edere m unca an terioar  a matematicienilor F rey , Serre
³i Rib et.
3. Criptograe p e curb e eliptice
Mai m ult  atenµie a fost îndreptat  spre folosirea curb ele eliptice în crip-
tograa cu c heie public , prima oar  ind propus  în lucr rile lui K oblitz ³i
Miller în an ul 1985. Motiv aµia utiliz rii curb elor eliptice în criptograe o con-
stituie inexsistenµa un ui algoritm sub-exp onenµial care s  rezolv e problema
agloritm ului discret p e o curb  eliptic .
Problema algoritm ului discret: Fie (G;) un grup ciclic de ordin n ³ig
un generator al grupului. Fiind date g;n c heia priv at  x este selectat aleator
în tre 1 ³in1 . Cheia public  se obµine astfel y=gx. Problema algoritm ului
discret presupune aarea lui x ind cunoscute grupul G ³ig;y;n .
Un a v an ta j al utiliz rii curb elor eliptice în criptograa cu c heie public 
este acela c  p en tru a asigura acela³i niv el de securitate este necesar  o c heie
de lungime mai mic . În tab elul de mai jos prezen t m comparativ lungimile
c heilor necesare p en tru RSA aplicat în Zn ³i p e curb e eliptice p en tru niv ele
de securitate diferite.
8

lungimile c heilor în bits RSAmodulon EC de ordin n
80 1024 160
112 2048 224
128 3072 256
192 8192 384
256 15360 512
9

3 Legea grupal  p e curb e eliptice p este corpuri
nite
P e baza form ulelor de adunare a punctelor p e curb e eliptice deduse din pro-
iectul [2], construim un algoritm care s  adune puncte p e curb e eliptice p este
corpuri nite. V om prezen ta mai în tâi co dul ³i ulterior v om da explicaµiile
necesare. Menµion m c  lim ba jul de programre folosit este Python. De ase-
menea a v em în v edere c  lucr m cu forma W eierstrass a curb elor eliptice,
deci p olinom ul cubic v a  de forma X3+a
X+b .
Observ aµie : A cest program lucreaz  cu corpuri de caracteristic  diferit 
de2 ³i3 .
from pip._vendor.distlib.compat import raw_input
a = int(raw_input("Introduceti primul coeficient: "))
b = int(raw_input("Introduceti al doilea coeficient: "))
x1 = int(raw_input("Abscisa primului punct: "))
y1 = int(raw_input("Ordonata primului punct: "))
x2 = int(raw_input("Abscisa al doilea punct: "))
y2 = int(raw_input("Ordonata al doilea punct: "))
p = int(raw_input("Numarul prim: "))
def gcd(a,b):
if a == 0:
return (b,0,1)
else:
g, x, y = gcd(b%a, a)
return (g, y – (b//a) *x, x)
def modularInverse(a,b):
g, x, _ = gcd(a,b);
if g == 1:
return (x%b)
def notMultipleRoots(a,b,p):
i=1
discriminant = -4 *a**3 – 27 *b**2
if (discriminant%p == 0):
i=0
return (i)
def pointsOnCurve(a, b, x1, x2, y1, y2, p):
10

v = x1 **3 + a *x1 + b
w = x2 **3 + a *x2 + b
j=1
if (v%p != (y1 **2)%p or w%p != (y2 **2)%p):
j=0
return (j)
def AddPoints(a, b, x1, x2, y1, y2, p):
if(x1 != x2):
if(x1<x2):
inv1 = modularInverse((x2-x1),p)
else:
inv1 = modularInverse((x2-x1+p),p)
y = y2-y1
slope = inv1 *y
x3 = (slope **2-x1-x2)%p
y3 = (slope *(x1-x3)-y1)%p
return (x3, y3)
elif (y1%p == y2%p):
if(y1%p == 0):
return ("Punctul de la infinit")
else:
inv2 = modularInverse(2 *y1, p)
slope = (3 *x1**2 + a) *inv2
x3 = (slope **2-x1-x2)%p
y3 = (slope *(x1-x3)-y1)%p
return(x3, y3)
else:
return("Punctul de la infinit")
def verifyEllipticCurve(a, b, x1, x2, y1, y2, p):
if( notMultipleRoots(a,b) == 0 ):
return("Nu este curba eliptica")
elif(pointsOnCurve(a, b, x1, x2, y1, y2, p) == 0):
return("Un punct nu se afla pe curba eliptica")
else:
return(AddPoints(a, b, x1, x2, y1, y2, p))
print (verifyEllipticCurve(a, b, x1, x2, y1, y2, p))
De la utilizitor se primesc ca input 7 n umere ³i an ume:
-a;b sun t co ecienµii corespunz tori p olinom ului cubic
X3+a
X+b2Fp[X] ;
-x1;y1 sun t co ordonatele prim ului punct;
-x2;y2 sun t co ordonatele celui de-al doilea punct;
11

-p este n um r natural prim corespunz tor corpului Fp p este care lucr m.
F uncµiagcd(a;b) determin , dup  cum îi sugereaz  n umele, cel mai mare
divizor com un al n umerelor a ³ib .
Exemplu :gcd(3456;76543) ia v aloarea 1 .
F uncµiamodularInverse (a;b) determin  prin recursivitate in v ersul lui amodulob ,
dac  acesta exist . P en tru a v erica dac  in v ersul lui amodulob exist  pu-
nem condiµia ca cel mai mare divizor com un al celor dou  n umere s  e
1 .
Exemplu :modularInverse (3456;76543) ia v aloarea 5692 .
F uncµianotMultipleRoots (a;b;p ) v eric  cu a jutorul discriminan tului dac 
p olinom ul cubic X3+a
X+b are r d cini m ultiple. •inem con t de faptul
c  p en tru un p olinom cubic de aceast  form , discriminan tul are v aloarea
(4)
a327
b2. Dac  v aloarea discriminan tul este 0 în corpul dat atunci
p olinom ul are r d cini m ultiple, ceea ce înseamn  c  n u p oate deni o curb 
eliptic .
Exemplu :notMultipleRoots (7;4;71) ia v aloarea 1i:e:
E(F71) =f(x;y)2F2
71:y2=x3+ 7
x+ 4g[fOg
este o curb  eliptic .
F uncµiapointsOnCurve (a;b;x 1;x2;y1;y2;p) v eric  dac  cele dou  puncte
date de utilizator sun t p e curba eliptic .
Exemplu :pointsOnCurve (7;4;15;17;43;24;71) ia v aloarea 1i:e: punc-
teleP(15;17);Q(43;24) sun t p e curba eliptic  E(F71) denit  mai sus.
F uncµiaAddPoints (a;b;x 1;x2;y1;y2;p) adun  dou  puncte de p e curba elip-
tic  urmând algoritm ul din proiectul "X".
Exemple :
AddPoints (7;4;15;17;43;24;71) ia v aloarea (53;9) ;
AddPoints (7;4;15;17;15;17;71) ia v aloarea (66;25) ;
AddPoints (1;3;12;3;11;6;17) ia v aloarea (3;4) ;
AddPoints (1;3;12;3;12;14;17) a³eaz  "Punctul de la innit".
F uncµiaverifyEllipticCurve se folose³te de funcµiile notMultipleRoots ³i
12

pointsOnCurve ca s  v erice c  toate condiµiile necesare p en tru adunarea
punctelor p e curba eliptic  sun t îndeplinite. Dac  sun t îndeplinit condiµiile
ap eleaz  funcµia AddPoints p enn tru a a³a rezultatul adun rii.
13

4 Izomorsme de grupuri
P en tru o mai bun  înµelegere a noµiunii de curb  eliptic  ne in tereseaz  s 
v edem izomorsme în tre grupurile de curb e eliptice ³i grupuri deja cunoscute.
V om a v ea nev oie de urm toarele rezultate.
T eorema de clasicare a grupurilor ab eliene nite :
Fie(G;
) un grup ab elian nit cu card(G) =n ; atunciG'Zd1:::Zds ,
unde 1<d 1; d1j:::jds (divizibilitatea are lo c în N ) ,d1
:::
ds=n .
Lem  :
Fiep prim impar astfel încât p2 (mod 3) ³iE(Fp) o curb  eliptic 
dat  de ecuaµia y2=x3+b . A tuncicard(E(Fp)) =p+ 1 .
Demonstraµie:
Ecuaµiay2=x3+b este ec hiv alen t  cu x3=y2b . Consider m funcµia
f:Z
p!Z
p
f(x) =x3:
Se observ   c  funcµia f este morsm de grupuri.
Presupunem prin absurd c  f n u este injectiv   i:e:9x2Ker(f);
x6= 1)x3= 1)ord(x) = 3 Din teorema lui Lagrange rezult  c  3
dividecard(Z
p)) =p1 Obµinem con tradicµia din faptul c  3 trebuie s  un
elemen t de forma 3
k+ 1 , undek este natural. Deci, f este injectiv  .
Cumf este morsm în tre dou  grupuri nite ³i este injectiv   rezult  c 
f este c hiar bijectiv  .
D m v alori lui y2f0;1;


;p1g ³i rezult  c  exist  exact p puncte
nite de forma (3p
y2b;y) . A d ug m ³i punctul de la innit ³i obµinem
p+ 1 puncte.
Exemplu :
Fie curba eliptic  E(F11) =f(x;y)2F11F11:y2=x3+ 3g: P en tru
a g si un izomorsm, a m mai în tâi cardinalul grupului E(F11) . Conform
lemei, a v em 12 elemen te în grup. Ne in tereseaz  cum arat  aceste elemen te,
iar p en tru aceasta v om în to cmi urm torul tab el:
14

xx3+ 3yPuncte
0 3 5;6(0;5);(0;6)
1 4 2;9(1;2);(1;9)
2 0 0 (2;0)
3 8
4 1 1;10(4;1);(4;10)
5 7
6 10
7 5 4;7(7;4);(7;7)
8 9 3;8(8;3);(8;8)
9 6
10 2
Nu uit m s  punem la calcul ³i punctul de la innit, notat cu O . Conform
teoremei de clasiare a grupurilor nite a v em c  E(F11) este izomorf cu Z12
sau cu Z2Z6 .
Cu a jutorul program ului de adunare a punctelor p e curb e elptice facem
tab ela adun rii p en tru E(F11) (v ezi pagina urm toare).
P en tru a decide care este izomorsm ul, ne uit m la ordinele elemen telor:
2
(0;5) = (0;5) + (0;5) = (0;6) ;
3
(0;5) = (0;5) + 2
(0;5) = (0;5) + (0;6) =O .
Rezult  c  ordin ul elemen tului este 3.
La fel pro ced m ³i p en tru celelalte puncte ³i obµinem:
ord((0;6)) = 3; ord ((1;2)) = 4; ord ((1;9)) = 4; ord ((2;0)) = 2;
ord((4;1)) = 12etc:
Deoarece grupul are 12 elemen te ³i a v em un elemen t de ordin 12 îmseamn 
c  grupul este ciclic. Cum din tre cele dou  grupuri, Z12;Z2Z6 , doar Z12
este ciclic r mâne c  grupul E(F11) este izomorf cu Z12 .
15

+O (0;5) (0;6) (1;2) (1;9) (2;0) (4;1) (4;10) (7;4) (7;7) (8;3) (8;8)
OO (0;5) (0;6) (1;2) (1;9) (2;0) )(4;1)(4;10) (7;4) (7;7) (8;3) (8;8)
(0;5) (0;5) (0;6)O (8;8) (4;1) (7;7) (8;3) (1;2) (2;0) (7;4) (1;9) (4;10)
(0;6) (0;6)O (0;5) (4;10) (8;3) (7;4) (1;9) (8;8) (7;7) (2;0) (4;1) (1;2)
(1;2) (1;2) (8;8) (4;10) (2;0)O (1;9) (0;5) (7;4) (8;3) (4;1) (0;6) (7;7)
(1;9) (1;9) (4;1) (8;3)O (2;0) (1;2) (7;7) (0;6) (4;10) (8;8) (7;4) (0;5)
(2;0) (2;0) (7;7) (7;4) (1;9) (1;2)O (8;8) (8;3) (0;6) (0;5) (4;10) (4;1)
(4;1) (4;1) (8;3) (1;9) (0;5) (7;7) (8;8) (7;4)O (1;2) (4;10) (2;0) (0;6)
(4;10) (4;10) (1;2) (8;8) (7;4) (0;6) (8;3)O (7;7) (4;1) (1;9) (0;5) (2;0)
(7;4) (7;4) (2;0) (7;7) (8;3) (4;10) (0;6) (1;2) (4;1) (0;5)O (8;8) (1;9)
(7;7) (7;7) (7;4) (2;0) (4;1) (8;8) (0;5) (4;10) (1;9)O (0;6) (1;2) (8;3)
(8;3) (8;3) (1;9) (4;1) (0;6) (7;4) (4;10) (2;0) (0;5) (8;8) (1;2) (7;7)O
(8;8) (8;8) (4;10) (1;2) (7;7) (0;5) (4;1) (0;6) (2;0) (1;9) (8;3)O (7;4)
16

Exemplu :
Fie curba eliptic  E(F7) =f(x;y)2F7F7:y2=x3+ 1g: P en tru a g si
un izomorsm, a m mai în tâi cardinalul grupului E(F7) . Pro ced m la fel ca
în exemplul an terior ³i construim tab elul p en tru a v edea elemen tele grupului.
xx3+ 1yPuncte
0 1 1;6(0;1);(0;6)
1 2 3;4(1;3);(1;4)
2 2 3;4(2;3);(2;4)
3 0 0 (3;0)
4 2 3;4(4;3);(4;4)
5 0 0 (5;0)
6 0 0 (6;0)
Ob esrv  m c  grupul are 12 elemen te. Conform teoremei de clasicare
a grupurilor nite rezult  c  E(Z7) p oate  izomorf cu Z12 sau cu Z2Z6 .
Calculând ordinele elemen telor obµinem c  n u exist  nici un elemen t de ordin
12 , deci grupul dat n u p oate  izomorf cu Z12 R mâne c  E(Z7) este izomorf
cuZ2Z6 .
Comen tariu :
Ne in tereseaz  aceste izomorsme de grupuri deoarece unele grupuri n u
sun t ciclice, v ezi exemplul an terior. Spre exemplu, în algoritm ul p en tru sem-
n turi digitale Die Hellman p e curb e eliptice ni se cere un generator al
grupului, iar dac  grupul n u este ciclic acesta n u exist . Deci n u putem
aplica algoritm ul Die Hellman p e orice curb  eliptic .
Comen tariu :
Ne în treb m dac  exist  o curb  eliptic  izomorf  cu grupul Z2Z6Z12 .
R spunsul la aceast  în trebare ni-l ofer  urm toarea teorem .
T eorem  :
FieE(Fq) o curb  eliptic  p este corpul nit Fq ; atunciE(Fq) este izomorf
cuZn , unden ste cardinlui curb ei eliptice, sau E(Fq) este izomorf cu Zn1
Zn2 , unde
n1;n1>1;n1jn2;n1jq1;n2jq1
.
17

5 Num rul de puncte al unei curb e eliptice
Am observ at c  o dat  ce cunoa³ten cardinalul unei curb e eliptice p este un
corp nit este u³or de spus cu ce grup este izomorf  aplicând teorema de
clasicare a grupurilor nite.
P en tru curb e eliptice p este corpuri nite cu un n um r mic de elemen te
am prezen tat în capitolul an terior o v arian t  p en tru a v edea punctele curb ei.
Îns  p en tru n umere mai acea meto d  este inecien t .
Ne propunem în cn tin uare s  prezen t m un algoritm mai ecien t de a n u-
m ra punctele unei curb e eliptice p este un corp nit. P en tru aceasta a v em
nev oie de câtev a rezultate.
Observ aµie : Fiep n um r prim, Fp corpul nit cu p elemen te,L o înc hi-
dere algebric  a lui Fp . A tunci p olinom ul f2L[X];
f(X) =XpX:
arep r d cini diferite în L .
Demonstraµie: Deriv ata formal  a acestui p olinom este
f0(X) =p
Xp11 =1;
cum deriv ata formal  n u se an uleaz  a v em c  toate r d cinile lui f sun t
simple. “tim c  în tr-o înc hiderea algebric  un p olinom de grad q are cel m ult
p r d cini. Din cele dou  armaµii obµinem c  p olinom ul
f(X) =XpX:
arep r d cini diferite în L .
Algoritm p olinomial Consider m curba eliptic  E(Fp) m ulµimea punctelor
ce satisfac ecuctia Y2=X3+A
X+B înFp .
Este u³or de calculat card(E(Fp))mod2 . Conform teoremei lui Lagrange
este sucien t s  a m fac  m ulµimea conµine elemen te de ordin 2 sau n u.
Dac  exist  cel puµin un elemen t de ordin 2 atuncicard(E(Fp))mod2 = 0 ,
altfelcard(E(Fp))mod2 = 1 . V om detalia pro cedeul de g sire a elemn telor
de ordin ul 2 ulterior în tr-un exemplu.
Datorit  teoremei Hasse este sucien t s  calcul m card(E(Fp))modl unde
l este prim ³i satisface proprietatea
Y
ll>4
sqrt(p):
18

P en tru a alfa n um rul de puncte al curb ei eliptice rezolv  m sistem ul ob-
µin ut cu lema c hinez  a resturilor. De menµionat este faptul c  o s  obµinem
o soluµie unic  a sistem ului deoarece lurile folosite sun t toate prime în tre
ele deoarece toate lurile sun t prime.
P en tru o mai bun  înµelegere a algoritm ului v om prezen ta un exemplu:
Fie curba eliptic  Y2=X3+X+ 13 p esteF31 . Observ  m c  v om calcula
card(E(Fp))modl p en trul2f2;3;5g . P en trul= 2 : V eric m dac  exist 
puncte de ordin ul 2 . “tim c  aceste puncte sun t de forma (x;0) ceea ce este
ec hiv alen t cu a spune c  x este r d cin  a p olinom ului X3+X+13 înF31[X] .
“tim din observ aµie c  p olinom ul
X31X
are toate r d cinile din mathbbF 31 . P en tru a v erica dac  p olinoam ul X3+
X+13 are r d cini în F31 este sucien t s  v eric m dac  cele dou  p olinoame
au r d cini com une. A cest lucru se reduce la a v erica dac 
g:c:d(X31X;X3+X+ 13)
.
calcule
R mâne c  card(E(Fp)mod2 = 0 .
Prin pro cedee asem n toare obµinem:
card(E(Fp)mod3 = 1;
card(E(Fp)mod35 = 4
V om notacard(E(Fp) =x .
Aplic m lema c hinez  a resturilor p en tru:8
><
>:xmod 2 = 0
xmod 3 = 1
xmod 5 = 4Calcul m
N= 2
3
5 = 30;
n1= 2)M1= 15 = 1mod2))y1= 151mod2 = 1
19

n2= 3)M2= 10 = 1mod3))y2= 101mod3 = 1
n3= 5)M3= 6 = 1mod5))y3= 61mod5 = 1
Rezult  c 
x= 0
15
1 + 1
10
1 + 4
6
1 = 34:
Conform teoremei de clasicare a grupurilor nite obµinem c  E(Fp) este
izomorf cu F34 .
20

Bibliograe
[1] C t lin Gherghe, Dorin P op escu, Cripto gr ae. Co duri. A lgoritmi , Editura
Univ ersit µii din Bucure³ti, 2005
[2] Anca Miron, Carmen Vîjiac, Gabriela Chirob o cea, Curb e eliptic e , 2017
[3] Ion D. Ion, Nicolae Radu, A lgebr   , Editura Didactic  ³i P edagogic  Bu-
cure³ti, 1991
[4] Andrew John Wiles, Mo dular el liptic curves and F ermat's L ast The or em ,
Annals of Mathematics, 1995
[5] Rene Sc ho of, Counting p oints on el liptic curve over nite elds , Journal
de theorie des nom bres de Bordeaux, 1995
[6] P an Y an Congruent Numb ers and El liptic Curves 2014
[7] Ian Blak e, Gadiel Seroussi, Nigel Smart, El liptic Curves in Crypto gr aphy ,
London Mathematical So ciet y Lecture Note Series, 1999
[8] Gabriela Chirob o cea, Corpuri nite , 2016
[9] h ttp://stac k o v ero w.com/questions/4798654/mo dular-m ultiplicativ e-
in v erse-function-in-p ython
21

Cuprins
1 Preliminarii 1
1.1 Notaµii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Deniµii, T eoreme . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Capitolul 1 7
3 Legea grupal  p e curb e eliptice p este corpuri nite 10
4 Izomorsme de grupuri 14
5 Num rul de puncte al unei curb e eliptice 18
Bibliograe 21
22