CURBE ELIPTICE

23
MODULUL 9 CURBE ELIPTICE Tema are ca scop prezentarea detaliată a curbelor eliptice, care stau la baza multor aplicaţii din criptografie precum şi din alte domenii ale informaticii. Curbele eliptice sunt menite să înlocuiască alte instrumente algebrice pentru proiectarea sistemelor criptografice cu chei publice, deoarece prezintă mai multă siguranţă. Studenţii vor întocmi o temă de casă care constă în rezolvarea problemelor şi exerciţiilor propuse. Cuvinte cheie: curbă eliptică, adunarea punctelor unei curbe eliptice, ordin al unui grup; ordin al unui element al unui grup. Indicaţii de studiere a temei: Timpul minim pe care trebuie să-l acordaţi studierii acestui modul este de 3 ore. Se citeşte cu atenţie şi se notează ideile principale, ecuaţiile matematice, se aprofundează noţiunile subliniate. Se apelează la literatura suplimentară indicată. Se parcurg întrebările de control şi testele de verificare. Se studiază problemele şi exerciţiile rezolvate. Se rezolvă exerciţiile propuse. Dacă nu se înţeleg rezolvările sau nu pot da soluţii unor probleme propuse se restudiază subiectul în cauză. Cuprins 9.1 Definiţii, notaţii. 9.2 Forme reduse ale ecuaţiei unei curbe eliptice. 9.3 Operaţia de adunare a punctelor unei curbe eliptice. 9.4 Metode generale pentru determinarea grupului unei curbe eliptice. 9.5 Relaţii de recurenţă pentru calculul multiplului unui punct. 9.6 Ordinul grupului unei curbe eliptice. 9.7 Cazuri particulare remarcabile privind ordinul grupului unei curbe eliptice. 9.8 Probleme rezolvate. 9.9 Teme pentru casă. După parcurgerea şi însuşirea acestei teme, studentul va cunoaşte: Forma generală a ecuaţiei unei curbe eliptice; Structura de grup a mulţimii punctelor unei curbe eliptice; Curbe eliptice peste unele corpuri finite; Ordinul grupului unei curbe eliptice; Ordinul unui element al unei curbe eliptice;

description

Fundamentele Algebrice Ale Informaticii

Transcript of CURBE ELIPTICE

Page 1: CURBE ELIPTICE

MODULUL 9CURBE ELIPTICE

Tema are ca scop prezentarea detaliată a curbelor eliptice, care stau la bazamultor aplicaţii din criptografie precum şi din alte domenii ale informaticii.Curbele eliptice sunt menite să înlocuiască alte instrumente algebrice pentruproiectarea sistemelor criptografice cu chei publice, deoarece prezintă mai multăsiguranţă.

Studenţii vor întocmi o temă de casă care constă în rezolvarea problemelor şiexerciţiilor propuse. Cuvinte cheie: curbă eliptică, adunarea punctelor unei curbe eliptice, ordin al unuigrup; ordin al unui element al unui grup.Indicaţii de studiere a temei: Timpul minim pe care trebuie să-l acordaţi studieriiacestui modul este de 3 ore.Se citeşte cu atenţie şi se notează ideile principale, ecuaţiile matematice, seaprofundează noţiunile subliniate. Se apelează la literatura suplimentară indicată. Separcurg întrebările de control şi testele de verificare. Se studiază problemele şiexerciţiile rezolvate. Se rezolvă exerciţiile propuse. Dacă nu se înţeleg rezolvările saunu pot da soluţii unor probleme propuse se restudiază subiectul în cauză.

Cuprins9.1 Definiţii, notaţii.9.2 Forme reduse ale ecuaţiei unei curbe eliptice.9.3 Operaţia de adunare a punctelor unei curbe eliptice.9.4 Metode generale pentru determinarea grupului unei curbe eliptice.9.5 Relaţii de recurenţă pentru calculul multiplului unui punct.9.6 Ordinul grupului unei curbe eliptice.9.7 Cazuri particulare remarcabile privind ordinul grupului unei curbe eliptice.9.8 Probleme rezolvate.9.9 Teme pentru casă.

După parcurgerea şi însuşirea acestei teme, studentul va cunoaşte: Forma generală a ecuaţiei unei curbe eliptice; Structura de grup a mulţimii punctelor unei curbe eliptice; Curbe eliptice peste unele corpuri finite; Ordinul grupului unei curbe eliptice; Ordinul unui element al unei curbe eliptice;

Page 2: CURBE ELIPTICE

9.1 DEFINIŢII, NOTAŢII

Curbele eliptice au fost puse în evidenţă de foarte multă vreme, ele furnizândobiecte remarcabile ale Geometriei algebrice. De dată mai recentă, cam din 1985 s-aremarcat utilitatea lor în criptografie. Până în prezent, au fost deja folosite în testareaprimalităţii, în descompunerea în factori a numerelor mari, precum şi în proiectareasistemelor criptografice.

Pentru că ne interesează în primul rând utilitatea acestor curbe în criptografie,vom avea în vedere aproape exclusiv cazul cel mai adecvat, şi anume: al curbeloreliptice definite peste corpuri finite.

O curbă eliptică Γ peste corpul comutativ F se defineşte printr-o ecuaţie deforma:

2 3 21 3 2 4 6y a xy a y x a x a x a , (1)

în care coeficienţii sunt elemente ale lui F. Se cere ca aceşti coeficienţi să fie astfelîncât ecuaţia să nu admită soluţii singulare, adică perechi de elemente x şi y ale lui Fcare să satisfacă atât ecuaţia (1), cât şi cele două ecuaţii obţinute din aceasta prinderivare în raport cu x şi cu y.

În general, o pereche (x,y) de elemente ale lui F se mai numeşte punct alplanului 2F şi se notează de obicei cu litere mari: P, Q,… Dacă perechea (x,y) estenotată cu P, atunci spunem că elementele x şi y sunt coordonatele lui P.

Se notează ( )F mulţimea punctelor ale căror coordonate satisfac ecuaţia(1), la care se adaugă un simbol O numit punctul de la infinit. Dacă un alt corp K îlconţine pe F, atunci Γ se poate considera curbă şi peste corpul K şi deci are sensmulţimea ( )K . Fireşte, această mulţime conţine mulţimea ( )F .

9.2 FORME REDUSE ALE ECUAŢIEI UNEI CURBEELIPTICE

O transformare a planului 2F în el însuşi definită prin ecuaţii de forma:

1 1 11 2 2 1

2 2 2; 0

x x yy x y

(2)

se numeşte transformare afină a planului.Evident că printr-o transformare afină ecuaţia (1) a curbei se poate modifica şi

vom căuta acele transformări care conduc la ecuaţii mai simple. De regulă cândaplicăm transformarea (2) ecuaţiei (1), revenim la vechile notaţii ale variabilelor,adică scriem din nou x în loc de x şi y în loc de y . Spunem pe scurt că înlocuim înecuaţia (1) pe x cu 1 1 1x y şi y cu 2 2 2x y Avem în vedereurmătoarele situaţii:

Cazul când caracteristica lui F este diferită de 2 şi de 3

Înlocuind în ecuaţia (1) pe y cu 1 312

y a x a , din această ecuaţie vor

dispărea termenii în xy şi y astfel că ecuaţia (1) va căpăta forma:

Page 3: CURBE ELIPTICE

2 3 22 4 6y x a x a x a . (3)

În acest caz putem da o formulare mai precisă condiţiei ca ecuaţia (3) să nuaibă puncte singulare, condiţie cerută prin definiţia curbei eliptice. Anume, sistemuldin care se obţin punctele singulare este:

2 3 22 4 6

22 43 2 0

2 0

y x a x a x a

x a x ay

(4)

iar acest sistem are soluţii dacă şi numai dacă polinomul din membrul drept al ecuaţiei(3) are rădăcini multiple.

Aşadar în cazul când caracteristica lui F este diferită de 2 ecuaţia (3) esteecuaţia generală a unei curbe eliptice, dacă polinomul din membrul drept nu arerădăcini comune cu derivata sa.

Mai menţionăm că dacă, în plus, caracteristica lui F este diferită nu numai de

2, ci şi de 3, atunci prin transformarea de înlocuire a lui x cu 23ax , în membrul

drept al ecuaţiei (3) va dispare termenul în 2x .Ca urmare, dacă F are caracteristica diferită şi de 2 şi de 3, atunci ecuaţia

generală a unei curbe eliptice este:2 3y x ax b , (5)

în care coeficienţii a şi b trebuie să fie astfel încât polinomul din membrul drept să nuaibă rădăcini multiple.

Cazul când caracteristica lui F este 2De astă dată dacă în ecuaţia (1) atât 1a , cât şi 3a sunt nuli, curba Γ va avea

puncte singulare. Într-adevăr, în acest caz ecuaţia obţinută prin derivarea ecuaţiei (1)în raport cu y va fi verificată pentru orice x şi y şi sistemul din care se obţin punctelesingulare devine:

2 3 22 4 6

22 40 3 2

y x a x a x a

x a x a

(6)

care are soluţii într-o extensie adecvată a corpului F. Aşadar coeficienţii 1a şi 3a dinecuaţia (1) nu pot fi amândoi nuli. Sunt posibile atunci următoarele două subcazuri.

Subcazul numit nesupersingular, în care a1 este diferit de zero

În acest caz înlocuind pe x cu 3

1

axa în ecuaţia (1) aceasta devine:

3 22 3 3 3 3

1 3 2 4 61 1 1 1

a a a ay a y x a y x a x a x aa a a a

Page 4: CURBE ELIPTICE

sau 2 3 21 2 4 6y a xy x a x a x a . În această ultimă ecuaţie înlocuind pe y cu

31a y şi pe x cu 2

1a x şi împărţind ecuaţia cu 61a , aceasta capătă forma:

2 3 22 4 6y xy x a x a x a . Înlocuind în această ultimă ecuaţie pe y cu

4y a se obţine următoarea formă:

2 3 2y xy x ax b , (7)

care este forma generală a ecuaţiei unei curbe eliptice nesupersingulare. Este uşor deverificat că această curbă are puncte singulare dacă şi numai dacă 0b .

Subcazul numit supersingular, în care a1 = 0Înlocuind în acest caz pe x cu 2x a ecuaţia (1) capătă forma:

2 33 3; 0y a y x ax b a , (8)

care este forma generală a ecuaţiei unei curbe eliptice supersingulare. Este uşor deverificat că oricare ar fi coeficienţii a şi b şi 3a nenul, curba nu poate avea punctesingulare.

În concluzie, fără a pierde generalitatea, ne putem limita la următoarele formereduse ale ecuaţiilor curbelor eliptice:

a) 2 3 22 4 6y x a x a x a dacă F are caracteristica diferită de 2.

Polinomul din membrul drept nu trebuie să aibă rădăcini multiple. Dacă, în plus, F arecaracteristica diferită şi de 3, atunci se poate considera 2 0a , adică forma redusă a

ecuaţiei unei curbe eliptice este: 2 3y x ax b ;

b) 2 3 2 ; 0y xy x ax b b sau 2 33 3; 0y a y x ax b a ,

dacă F are caracteristica egală cu 2. Aceste două mulţimi de curbe sunt disjuncte.

9.3 OPERAŢIA DE ADUNARE A PUNCTELOR UNEICURBE ELIPTICE

Pentru definirea operaţiei de adunare pe mulţimea ( )F trebuie menţionatrolul convenţional al „punctului de la infinit” notat cu O. Următoarele grupe de regulidefinesc această operaţie.

Reguli convenţionale (în care intervine punctul O)I. Convenţia elementului neutru.Pentru orice punct P al curbei, avem:

O + P = P + O = P, (9)

relaţia fiind adevărată şi pentru P = O. Aşadar punctul O are rolul de element neutrual operaţiei.

II. Convenţia elementului opus.

Page 5: CURBE ELIPTICE

Dacă 1x şi 1y sunt coordonatele unui punct P ≠ O al curbei, atunci înlocuindîn ecuaţia curbei pe x cu 1x se obţine o ecuaţie de gradul doi în y, pentru care 1y esteuna din soluţii. Fie 2y cealaltă soluţie. Notăm –P punctul având coordonatele 1x şi

2y . Cu această notaţie postulăm:

P + (–P) = (–P) + P = O, (10)

adică punctul notat –P se comportă în această operaţie ca opusul lui P.Elementul 2y se poate preciza în funcţie de forma redusă a ecuaţiei pe care o

folosim.- Dacă folosim forma redusă 2 3 2

2 4 6y x a x a x a (deci încazul când caracteristica lui F este diferită de 2), atunci 2 1y y .

- Dacă folosim forma redusă 2 3 2 ; 0y xy x ax b b (când Fare caracteristica 2 şi curba este nesupersingulară), atunci 1 2 1y y x şi deci

2 1 1y y x .

- Dacă folosim forma redusă 2 33 3; 0y a y x ax b a (când

F are caracteristica doi şi curba este supersingulară), atunci 1 2 3y y a şi deci

2 1 3y y a .Remarcăm faptul că dacă două puncte diferite de O ale curbei au aceeaşi

abscisă, atunci ele sunt sau opuse unul altuia sau coincid. (Aceste situaţii nu suntdisjuncte: de exemplu, dacă ecuaţia curbei este 2 3 2

2 4 6y x a x a x a şi 1xeste o rădăcină a polinomului din membrul drept, atunci punctul 1P de coordonate 1xşi 0 este propriul lui opus).

Deci în deducerea formulelor de adunare a punctelor diferite de O avem deconsiderat două cazuri, după cum abscisele lor sunt distincte (caz în care punctele suntdistincte) şi cazul în care abscisele sunt egale. În acest din urmă caz, dacă punctelesunt distincte, atunci ele sunt opuse unul altuia şi deci se aplică convenţia menţionatăpentru adunare. Aşadar dacă abscisele celor două puncte ce urmează a se aduna suntegale, atunci vom considera numai situaţia când cele două puncte coincid.

Pentru deducerea formulelor de adunare a punctelor diferite de O vor trebuifolosite pe rând cele trei forme reduse ale ecuaţiei curbei.

Adunarea punctelor curbei când caracteristica lui f este diferită de 2

Ecuaţia curbei este în acest caz: 2 3 22 4 6y x a x a x a . Fie 1 1,x y ,

2 2,x y coordonatele punctelor 1P , respectiv 2P ale curbei şi ne propunem să

determinăm coordonatele 3x şi 3y ale opusului sumei 1 2P P .Sunt de considerat două cazuri, după cum abscisele celor două puncte sunt

diferite sau egale.

Page 6: CURBE ELIPTICE

Cazul x1 ≠ x2

Punctele distincte 1P şi 2P determină o dreaptă care intersectează curba înpunctele 1P şi 2P şi încă într-un punct 3P , bine determinat, deoarece ecuaţia curbeiare gradul trei. Se defineşte 1 2 3P P P .

Pentru determinare coordonatelor 3x şi 3y ale lui 3P considerăm ecuaţiadreptei determinate de punctele distincte 1P şi 2P :

2 11 1

2 1

y yy y x xx x

. (11)

Înlocuind pe y din această ecuaţie în ecuaţia (3) a curbei, aceasta devine:

2

3 22 11 1 2 4 6

2 1

y yy x x x a x a x ax x

. (12)

Această ecuaţie de gradul trei are evident rădăcinile 1x şi 2x , deoarece 1P şi

2P sunt puncte ale curbei, astfel că a treia rădăcină se obţine din prima formulă a luiViète:

22 1

3 1 2 22 1

y yx x x ax x

. (13)

Înlocuind în relaţia (11) se obţine:

2 13 1 3 1

2 1

y yy y x xx x

. (14)

Aşadar coordonatele punctului 3P sunt date de relaţiile (13) şi (14).Menţionăm că punctul 3P nu este exact suma 1 2P P , ci este opusul acesteia. Pentrua obţine coordonatele sumei 1 2P P se înlocuieşte 3y cu 3y .

În cazul când caracteristica lui F este diferită şi de 3, atunci în aceste formulese poate lua 2 0a .

Cazul când x1 = x2

Aşa cum am menţionat, în acest caz avem de considerat numai situaţia când şi1y este egal cu 2y , adică punctele 1P şi 2P coincid.

Tangenta la curbă în punctul 1P va intersecta curba (de gradul trei) în punctul

1P , ca punct dublu, şi deci o va mai intersecta încă într-un punct bine determinat 3P .Se defineşte suma 1 1 3P P P .

Ecuaţia implicită a curbei este: 2 3 22 4 6( , )f x y y x a x a x a şi

pentru ecuaţia tangentei în 1P , aplicând formula:1 11 1( ) ( ) 0y xy y f x x f . Se

obţine astfel ecuaţia tangentei:

Page 7: CURBE ELIPTICE

21 1 1 1 2 1 42 3 2 0y y y x x x a x a . (15)

Remarcăm că dacă 1 0y , atunci 1 1P P şi deci 1 1P P O potrivitregulii enunţate mai înainte. Aşadar, considerând 1 0y din ecuaţia (15) se poateexplicita y, şi anume:

21 2 1 4

1 11

3 22

x a x ay y x xy

(16)

pe care înlocuindu-l în ecuaţia (3) a curbei aceasta devine:

22

3 21 2 1 41 1 2 4 6

1

3 22

x a x ay x x x a x a x ay

. (17)

Această ecuaţie de gradul trei are rădăcina dublă 1x x şi deci a treiarădăcină se obţine iarăşi din prima formulă a lui Viète:

221 2 1 4

3 1 21

3 2 22

x a x ax x ay

(18)

care, înlocuit în (16), dă pe 3y :

21 2 1 4

3 1 3 11

3 22

x a x ay y x xy

. (19)

Formulele (18) şi (19) dau coordonatele opusului punctului 1 1P P . Pentru aobţine coordonatele sumei 1 1P P (care se mai scrie 12P ) se înlocuieşte 3y cuopusul său, adică 3y .

În cazul când caracteristica lui F este diferită şi de 3, atunci în formulele (18)şi (19) se poate lua 2 0a .

Adunarea punctelor când F are caracteristica 2 şi curba este nesupersingulară

Ecuaţia curbei este în acest caz: 2 3 2 ; 0y xy x ax b b . Precizăm căîn cazul corpurilor de caracteristică 2 adunarea se confundă cu scăderea şi deci vomfolosi numai semnul adunării.

Cazul x1 ≠ x2

Înlocuind, ca mai înainte, 2 11 1

2 1

y yy y x xx x

în ecuaţia curbei

aceasta devine:

2

3 22 1 2 11 1 1 1

2 1 2 1

y y y yy x x x y x x x ax bx x x x

.

Page 8: CURBE ELIPTICE

Această ecuaţie de gradul trei în x are două rădăcini cunoscute, 1x şi 2x , iar atreia rădăcină o aflăm folosind prima formulă a lui Viète:

22 1 2 1

3 1 22 1 2 1

y y y yx x x ax x x x

, (20)

de unde se obţine:

2 13 1 3 1

2 1

y yy y x xx x

. (21)

Precizăm iarăşi că pentru a obţine suma 1 1P P se înlocuieşte 3y cu

3 3y x .

Cazul x1 = x2

Avem de efectuat suma 1 1P P care se mai scrie 12P . Se consideră atunci

tangenta în 1P la curba de ecuaţie implicită 2 3 2( , )f x y y xy x ax b .

Ecuaţia tangentei este: 21 1 1 1 1 0y y x x x y x , unde am ţinut seamă

că F are caracteristica 2.Dacă 1 0x , atunci opusul 1P va avea a doua coordonată egală cu

1 1 1y x y , adică aceeaşi ca şi 1P , deci 1 1P P , de unde rezultă că 1 1P P O .Dacă 1 0x , atunci se poate explicita x din ecuaţia tangentei şi înlocuindu-l

în ecuaţia curbei aceasta devine o ecuaţie de gradul trei care are ca rădăcină dublă pe1x :

2

3 21 11 1 1 1 1 1

1 1

y yy x x x x y x x x x ax bx x

.

A treia rădăcină o obţinem folosind iarăşi prima formulă a lui Viète:2 2 3 2

2 2 21 1 1 1 1 1 13 1 1 1 12 2

1 1 1 1

y y y x y x ax bx x x a x xx x x x

(22)

şi apoi din ecuaţia tangentei rezultă:

2 2 2

2 21 1 1 1 1 13 1 3 1 1 3 1 1 1 3

1 1 1

y x y x y xy y x x y x y x x xx x x

. (23)

Pentru a se obţine punctul 12P se înlocuieşte 3y cu 3 3y x .

Adunarea punctelor când f are caracteristica 2, iar curba este supersingulară

Ecuaţia redusă a curbei în acest caz este: 2 33 3; 0y a y x ax b a .

Page 9: CURBE ELIPTICE

Cazul x1 ≠ x2

Înlocuind 2 11 1

2 1

y yy y x xx x

în ecuaţia curbei aceasta devine:

2

32 1 2 11 1 3 1 1

2 1 2 1

y y y yy x x a y x x x ax bx x x x

,

de unde se obţine la fel ca mai înainte:2

2 13 1 2

2 1

y yx x xx x

; (24)

şi

2 13 1 3 1

2 1

y yy y x xx x

. (25)

Cazul x1 = x2

Din ecuaţia implicită a curbei: 2 33( , )f x y y a y x ax b se obţine

ecuaţia tangentei în punctul 1P la curbă: 21 3 1 1 0y y a x x x a , de

unde înlocuind 21

1 13

x ay y x xa

în ecuaţia curbei, aceasta devine:

22 2

31 11 1 3 1 1

3 30x a x ay x x a y x x x ax b

a a

Ecuaţia are rădăcina dublă 1x x , iar a treia rădăcină este:

22 4 21 1

3 23 3

x a x axa a

(26)

şi

21

3 1 3 13

x ay y x xa

, (27)

dacă 1 2P P .În ambele cazuri, pentru a se obţine suma, se înlocuieşte 3y cu 3 3y a .

Tabelul prezintă lista formulelor de adunare a punctelor unei curbe eliptice.

Operaţia definită pe mulţimea ( )F a punctelor unei curbe eliptice are,evident, proprietăţile de comutativitate, are element neutru, şi anume punctul O de la

Page 10: CURBE ELIPTICE

infinit şi pentru orice punct P s-a definit opusul său. Ca să fie grup mai trebuieproprietatea de asociativitate. Această proprietate este adevărată, dar verificarea eipresupune un calcul destul de amplu. Există şi alte demonstraţii ale asociativităţii, darcare nu vor fi prezentate în această expunere.

Page 11: CURBE ELIPTICE

Ecuaţia curbei 1 2 1 2 ( )P P P P 1 1 12P P P 2

2 13 1 2

2 1

y yx x xx x

221

3 11

3 22

x ax xy

2 3y x ax b

(car. F > 3) 2 1

3 1 3 12 1

y yy y x xx x

21

3 1 3 11

32

x ay y x xy

22 1

3 1 2 22 1

y yx x x ax x

221 2 1 4

3 1 21

3 2 22

x a x ax x ay

2 3 2

2 4 6y x a x a x a (car. F = 3)

2 13 1 3 1

2 1

y yy y x xx x

21 2 1 4

3 1 3 11

3 22

x a x ay y x xy

22 1 2 1

3 1 22 1 2 1

y y y yx x x ax x x x

23 1 2

1

bx xx

2 3 2 ; 0y xy x ax b b

(car. F = 2; nesupersingular) 2 1

3 1 3 1 32 1

y yy y x x xx x

22 1 1

3 1 3 31

y xy x x xx

22 1

3 1 22 1

y yx x xx x

4 21

3 23

x axa

2 3

3 3; 0y a y x ax b a (car. F = 2; supersingular)

2 13 1 3 1 3

2 1

y yy y x x ax x

21

3 1 3 1 33

x ay y x x aa

Page 12: CURBE ELIPTICE

9.4. METODE GENERALE PENTRU DETERMINAREAGRUPULUI UNEI CURBE ELIPTICE

Mulţimea punctelor curbei se obţine înlocuind pe x din ecuaţia curbei succesivcu elementele corpului F. Pentru fiecare element 0x al lui F se obţine o ecuaţie degradul doi în y. Dacă această ecuaţie are două rădăcini distincte, atunci obţinem douăpuncte ale curbei care sunt opuse unul altuia. Dacă ecuaţia are două rădăcini egale, seobţine un punct care este propriul său opus, adică are ordinul 2. Dacă ecuaţia în y nuare nici o soluţie, atunci curba nu are nici un punct de abscisă 0x .

În cazul când caracteristica lui F este diferită de 2 ecuaţia curbei Γ are formagenerală 2 ( )y f x , unde 3 2 3

2 4 6( ) sauf x x a x a x a x ax b . Dacă

pF Z este un corp de clase de resturi, atunci pentru rezolvarea ecuaţiei2

0( )y f x se foloseşte simbolul lui Lagrange şi algoritmul de calculare a rădăcinii

pătrate. Dacă F este o extindere (finită) a unui pZ , având nq p elemente atunci

pentru rezolvabilitatea ecuaţiei se verifică dacă 1

20( ) 1q

f x (se foloseşte

exponenţierea modulară) şi în caz că această condiţie este îndeplinită rădăcinilepătrate ale lui 0( )f x se află printr-un algoritm asemănător celui din pZ .

În ce priveşte numărul punctelor grupului nu există o formulă generală pentruexprimarea acestuia.

Putem spune totuşi că numărul maxim de puncte s-ar obţine atunci când pentrutoate cele q valori ale lui 0x ecuaţia în y are două rădăcini distincte. Grupul ar aveaatunci 2q + 1 elemente. Această performanţă este atinsă de curba Γ3 supersingularădefinită peste 2F Z (ea are 5 puncte şi este definită prin ecuaţia 2 3y y x x )şi de a cincea curbă din tabelul celor 10 curbe eliptice definite peste 3F Z (ea are 7

puncte şi este definită prin ecuaţia: 2 3 1y x x ). Nici una din cele 20 de curbeeliptice definite peste 5F Z nu atinge această performanţă (ar trebui să aibă 11puncte).

Numărul minim de puncte (diferite de punctul de la infinit) al unei curbeeliptice este zero. Aceasta se întâmplă atunci când pentru toate valorile lui 0x ecuaţiaîn y nu are nici o soluţie. Pentru 2F Z se află în această situaţie curba

supersingulară 4 de ecuaţie 2 3 1y y x x . Pentru 3F Z semnalăm curba

cu numărul 6 din tabelul corespunzător, definită de ecuaţia: 2 3 1y x x .În cazul caracteristicii diferite de 2 putem aprecia valoarea medie statistică a

ordinului grupului unei curbe eliptice. Pornind de la faptul că elementele nenule alecorpului se împart în două clase egale – cele care sunt şi cele care nu sunt pătrate –elementul 0( )f x are şanse egale să fie sau să nu fie un pătrat. Deci jumătate din celeq – 1 valori ale lui 0x vor conduce la ecuaţii în y care vor avea fiecare două soluţii.

Page 13: CURBE ELIPTICE

Aşadar valoarea medie a numărului elementelor grupului unei curbe eliptice esteaproximativ egală cu q, numărul elementelor corpului F.

Aşa cum arată exemplele prezentate mai sus marea împrăştiere privind ordinulgrupului se manifestă şi în ce priveşte tipul acestuia. Grupuri de acelaşi ordin pot fi detipuri foarte diferite.

Procedeul cel mai frecvent folosit pentru stabilirea tipului curbei constă încalcularea ordinului diverselor puncte ale curbei, luate la întâmplare. Dacă secunoaşte ordinul grupului şi găsim un punct al cărui ordin este egal cu ordinulgrupului, deducem că grupul este ciclic, iar acel punct este un generator al grupului.Putem atunci identifica toţi ceilalţi generatori.

Ordinul unui punct se obţine adunând acel punct cu el însuşi de atâtea ori pânăse ajunge la opusul său, adică atunci când abscisa devine egală cu cea a punctului cucare s-a pornit. Se poate stabili o relaţie de recurenţă pentru adunarea succesivă a unuipunct cu el însuşi.

9.5. RELAŢII DE RECURENŢĂ PENTRU CALCULULMULTIPLULUI UNUI PUNCT

Considerăm, pentru simplitate, cazul când curba are ecuaţia2 3y x ax b . Notând 1 1,x y coordonatele punctului 1P al curbei şi ,n nx y

coordonatele punctului 1nP folosim formulele2

2 13 1 2

2 1

y yx x xx x

,

2 13 1 3 1

2 1( )y yy y x x

x x

pentru calculul coordonatelor punctului 1( 1)n P ,

luând ,n nx y în loc de 2 2,x y :

21

1 11

nn n

n

y yx x xx x

; 11 1 1 1

1

nn n

n

y yy y x xx x

; 1n . (28)

Pentru 1n se folosesc formulele de calculare a coordonatelor lui 12 P :

221

2 11

3 22

x ax xy

; 21

2 1 2 11

32

x ay y x xy

. (29)

Dacă se lucrează cu ordine foarte mari ale corpului F, deci şi al grupuluicurbei, aşa cum cere siguranţa sistemelor criptografice, atunci în loc să calculămsuccesiv multiplii unui punct până ajungem să găsim ordinul său, s-ar putea să neintereseze anumiţi multipli (foarte mari) ai punctului. Folosim atunci procedeul„multiplicării modulare”, bazat pe exprimarea factorului de multiplicare în baza 2.Calculăm atunci succesiv multiplii 12n P prin formule de recurenţă deduse dinformulele (29):

22

13 2

2n

n nn

x ax xy

; 2

1 13

2n

n n n nn

x ay y x xy

, (30)

Page 14: CURBE ELIPTICE

în care ,n nx y sunt coordonatele punctului 112n P .

9.6. ORDINUL GRUPULUI UNEI CURBE ELIPTICEExemplele prezentate mai sus arată că grupurile curbelor eliptice prezintă o

mare diversitate atât în ce priveşte tipul, cât şi în privinţa ordinului. Nu se poate da oformulă care să ofere ordinul unui astfel de grup.

Totuşi, dacă se cunoaşte ordinul N al unei curbe eliptice Γ pe corpul finit F,atunci se poate determina ordinul grupului ( )K pentru orice extensie finită K a luiF.

Avem în vedere cazul general sub aspectul că F este un corp finit oarecare şinotăm q numărul elementelor sale (adică F nu este, ca în exemplele anterioare un corpde clase de resturi, pZ , faţă de un număr prim p). Corpul cuprinzător, K, al lui F va

avea numărul de elemente de forma nq . Dacă p este caracteristica lui F, atunci qînsuşi va fi o putere a lui p.

Menţionăm în plus, că pentru orice număr natural n, nenul, există o extensie Ka lui F având nq elemente şi orice două astfel de extensii sunt izomorfe.

Dată fiind curba Γ definită pe corpul F, pentru orice număr natural nenul n,curba va fi evident definită peste extinderea K a lui F, având nq elemente. Fie nNordinul grupului ( )K . În particular, 1N N . Se obţine şirul de numere naturale

nN , evident crescător. Următoarea teoremă arată că termenii acestui şir se pot calculadacă se cunoaşte primul termen îN N .

TEOREMA LUI HASSE

Fie seria formală de puteri 1

1

( , ) en

nn

N TnZ T

numită funcţia zeta acurbei Γ. Este adevărată următoarea egalitate:

21( , )(1 )(1 )

aT qTZ TT QT

, (31)

în care 1a q N . În plus, este îndeplinită egalitatea: 2 4a n , adică polinomulde la numărătorul fracţiei din relaţia (7.31) are sau rădăcini complexe nereale, saureale şi egale.

Demonstraţia se găseşte în cartea lui I. Silverman, The Arithmetic of EllipticCurves, Springer Verlag, 1986.

Vom arăta în continuare cum se foloseşte această teoremă pentru a determinanumerele nN în funcţie de N.

COROLARPentru orice număr natural nenul n este îndeplinită egalitatea:

1n n nnN q , (32)

Page 15: CURBE ELIPTICE

în care α este una din rădăcinile polinomului 2T aT q , adică:

21 1 1aT qT T T .

DEMONSTRAŢIEPrecizăm mai întâi că expresia „serie formală” din enunţul teoremei lui Hasse

se referă la faptul că nu ne interesează convergenţa acestor serii, ci numai operaţiilealgebrice cu acestea. Astfel, dacă u este o serie de puteri atunci eu înseamnă

0

1!

n

nu

n

, iar logaritmarea seriilor înseamnă inversa operaţiei de exponenţiere, adică,

prin definiţie, ln eu u . În plus, vom folosi faptul că1

1ln(1 ) n

nu u

n

.

Ţinând seamă de aceste relaţii, logaritmând egalitatea (31), obţinem:

2

1

1 1 1 1

1 1 (1 ) (1 )ln ln(1 )(1 ) (1 )(1 )

1 1 1 1 1 .

nn

n

n n n n n n n n n n nn

n n n n

aT qT T TN Tn T qT T qT

T T T q T N qn n n n

Observăm că pentru 1n formula obţinută devine:1 1 1N q q a , ceea ce rezultă şi din definiţia lui a. Q.E.D.

De remarcat faptul că teorema lui Hasse conţine şi afirmaţia că 2 4a q deunde rezultă:

1

12 2

1

2 2 2 1 2

1 2 1 2

( 1) ( 1)

q a q q q N q

q q N q q

q N q

Cum curba Γ este definită pentru orice extensie K a lui F, având nq elemente,formula obţinută este valabilă pentru orice n, adică:

2 21 1 ; 1n n

nq N q n . (33)

Când n sau q sunt foarte mari (ceea ce este cazul curbelor eliptice folosite în

criptografie), putem considera 21n nq q , de unde rezultă că numărul

punctelor unei curbe eliptice variază în limite neglijabile în jurul număruluielementelor corpului.

Page 16: CURBE ELIPTICE

Inegalităţile (33) sunt îndeplinite de curbele eliptice definite peste

2 3 5, ,F Z Z Z . Într-adevăr, pentru q = 2 (şi n = 1) limitele sunt 22 1 , adică

1 şi 5. Cele 6 curbe eliptice peste 2Z au ordinele: 1, 2, 3, 3, 4, 5.Pentru q = 3 (şi, fireşte, n = 1) cele 10 curbe definite peste 3Z au ordinele

cuprinse între 1 şi 7 şi tocmai acestea sunt limitele date de teorema lui Hasse.Pentru q = 5 cele 20 de curbe definite peste 5Z au ordinele cuprinse între 2 şi

9, iar limitele rezultate din teorema lui Hasse sunt 25 1 , adică 2 şi 10.

9.7. CAZURI PARTICULARE REMARCABILE PRIVIND ORDINULGRUPULUI UNEI CURBE ELIPTICE

În formula 1n n nnN q numerele complexe α şi conjugatul său

sunt rădăcinile polinomului 2T aT q unde pe de o parte 1a q N , în care

N este ordinul grupului ( )F , iar pe de altă parte 2 4a q . Ne interesează cazul

limită când 2 4a q , când cele două rădăcini vor fi deci reale şi egale. Observăm că:

22 4 2 1a q a q N q .

Rezultă că această relaţie nu se poate îndeplini decât dacă q este un pătratperfect, mai precis, o putere pară a caracteristicii corpului. Oricum dacă q este unnumăr prim p relaţia 2 4a q nu poate fi satisfăcută.

Căutăm atunci cazul cel mai simplu 2q p şi ne propunem să găsim condiţiace trebuie să o îndeplinească curba eliptică Γ definită peste pZ astfel ca această

curbă, considerată peste extinderea K a lui pZ având 2q p elemente, săîndeplinească condiţia:

2 2 2

2 1 1 1 2N q p p p . (34)

Deoarece 2 2 22 1N p , relaţia (12.34) este echivalentă cu:

2 2 2 p . Dar 2 2 2 2( ) 2 2a p şi deci relaţia

(12.34) este echivalentă cu: 2 2 2a p p . Sunt deci posibile două cazuri:2 4a p sau 0a . Primul se respinge, deoarece a este număr întreg, iar p este

număr prim. Rămâne numai situaţia 0a , adică 1 1N N p .Condiţia 1N p este îndeplinită, în cazul 2p de curbele

supersingulare Γ1 şi Γ2, pentru 3p de primele 4 curbe din tabelul celor10 curbe eliptice definite peste 3Z şi în cazul p = 5 de primele 4 şi a 16-a din tabelulcelor 20 de curbe eliptice definite peste 5Z .

Page 17: CURBE ELIPTICE

Reţinem deci cazul 0a , care este consistent, în sensul că există curbedefinite peste pZ care îndeplinesc această condiţie. În acest caz una din rădăcinile

polinomului 2T aT q este i p şi deci:

2 2

2

0; 4 1

i ( i) 2 ; 4

2 ; 4 2.

n nn n n n

n

n m

p p n m

p n m

(35)

În concluzie, dacă o curbă Γ definită peste corpul pZ are 1p elemente,atunci:

2

2

1; 4 1

1 2 ; 4

1 2 ; 4 2.

n

nn

nn

n

p n m

N p p n m

p p n m

(36)

9.8. PROBLEME REZOLVATE9.8.1. Să se determine curbele eliptice supersingulare definite peste Z2 şi grupurilecorespunzătoare

Rezolvare

Ecuaţia generală a unei astfel de curbe este 2 33 3; 0y a y x ax b a .

Condiţia 3 0a înseamnă 3 1a , deoarece 2Z are numai două elemente. Se obţinurmătoarele 4 curbe:

2 3 2 31 2

2 3 2 33 4

: ; : 1;

:

şi : 1.y y x y y x

y y x x y y x x

Curba Γ1

În afară de punctul O celelalte puncte se obţin dând lui x valorile 0 şi 1. Pentru0x obţinem două valori pentru y, şi anume: 1 0y şi 2 1y , iar pentru 1x

ecuaţia în y nu are nici o soluţie în 2Z . Punctele obţinute pentru 0x sunt, potrivitdefiniţiei, opuse unul altuia.

Aşadar, curba are trei puncte şi deci grupul acestei curbe este izomorfcu 3Z .

Page 18: CURBE ELIPTICE

Curba Γ2

De data asta ecuaţia în y nu are soluţii pentru 0x şi are două soluţii pentru1x . Grupul curbei este din nou izomorf cu 3Z .

Curba Γ3

Atât pentru 0x , cât şi pentru 1x ecuaţia în y are două soluţii. Prinurmare, grupul curbei are 5 puncte O; (0,0); (0,1); (1,0) şi (1,1).

Punctul al doilea şi al treilea sunt opuse unul altuia şi la fel ultimele două,pentru că au aceeaşi abscisă.

Ordinul grupului fiind egal cu numărul prim p = 5 înseamnă că grupul esteizomorf cu 5Z .

Curba Γ4

Ecuaţia în y nu are soluţii nici pentru 0x şi nici pentru 1x . Prin urmare,curba are numai un singur punct şi anume punctul O.

9.8.2. Să se determine curbele eliptice nesupersingulare definite peste Z2 şi grupurilecorespunzătoare

RezolvareEcuaţia generală a unei astfel de curbe este 2 3 2 ; 0y xy x ax b b ,

în care condiţia 0b înseamnă 1b , deci se obţin numai două curbe:2 3 2 3 2

1 2: 1 : 1y xy x y xy x x .

Curba Γ1

Pentru 0x ecuaţia în y are o singură soluţie şi se obţine punctul (0,1) careeste propriul său opus. Pentru 1x ecuaţia în y are două soluţii şi se obţin punctele(1,0) şi (1,1) care nu sunt fiecare propriul său opus, deoarece ele sunt opuse unulaltuia. Prin urmare ele nu sunt elemente de ordinul 2.

Deoarece grupul are 4 elemente el este izomorf sau cu 4Z sau cu 2 2Z Z . Încazul al doilea ar trebui ca toate elementele în afară de O să aibă ordinul doi, ceea cenu este adevărat. Deci, grupul curbei este izomorf cu 4Z .

Curba Γ2

Pentru 0x ecuaţia în y are o singură soluţie, iar punctul pe care-l defineşteeste propriul său opus. Pentru 1x ecuaţia în y nu are nici o soluţie.

Prin urmare, grupul curbei are două elemente şi deci este izomorf cu 2Z .

9.8.3. Să se determine curbele eliptice definite peste Z3 şi grupurile corespunzătoare

RezolvareEcuaţia generală a unei astfel de curbe este 2 3 2y x ax bx c , deci

sunt de considerat în total 33 = 27 ecuaţii. Dintre acestea reţinem numai pe acelea încare polinomul din membrul drept nu are rădăcini multiple.

Page 19: CURBE ELIPTICE

Pe de altă parte ne putem restrânge la un număr mai mic de ecuaţii folosindtransformări ale coordonatelor. Înlocuind pe x cu x + m în ecuaţie, coeficientul lui 2xrămâne tot a, iar al lui x devine 2am + b.

Sunt deci de considerat două cazuri, după cum 0a sau 0a , în acest dinurmă caz 1a .

Dacă 0a , iar b şi c iau independent valorile zero şi ±1, se obţin următoarele9 polinoame în membrul drept al ecuaţiei curbei: 3x , 3 1x , 3x x , 3 1x x .Primul are, evident, rădăcini multiple, dar şi următoarele două, deoarece

3 31 ( 1)x x . Celelalte au derivata egală cu ±1 şi deci nu au rădăcini multiple.

Aşadar în acest caz reţinem 6 ecuaţii de curbe eliptice: 2 3y x x şi2 3 1y x x .

Dacă 0a , atunci luând m = -b/2a, se poate considera coeficientul lui x cafiind nul şi obţinem ecuaţiile de forma: 2 3 2y x x c . Dacă 0c polinomuldin membrul drept va avea rădăcina dublă 0x , iar dacă 1c , atunci polinomuldin membrul drept nu are rădăcini multiple. Deci reţinem4 ecuaţii de curbe eliptice: 2 3 2 1y x x .

În următorul tabel precizăm grupurile definite de aceste curbe.

Page 20: CURBE ELIPTICE

Nr. Ecuaţia curbei Punctele curbei Grupulcurbei

1 2 3y x x O; (0,0); (–1,1); (–1,–1) 4Z2 2 3y x x O; (0.0); (1,0); (–1,0) 2 2Z Z3 2 3 1y x x O; (1,0); (0,1); (0,–1) 4Z4 2 3 1y x x O; (1,1); (1,–1); (–1,0) 4Z

5 2 3 1y x x O; (0,1); (0,–1); (1,1); (1,–1);(–1,1); (–1,–1) 7Z

6 2 3 1y x x O {O}

7 2 3 2 1y x x O; (0,1); (0,–1); (1,0); (–1,1); (–1,–1) 6Z8 2 3 2 1y x x O; (1,1); (1, –1) 3Z9 3 3 2 1y x x O; (0,1); (0,–1); (1,1); (1,–1) 5Z10 2 3 2 1y x x O; (–1,0) 2Z

Pentru ultimele 6 curbe ordinul grupului determină tipul său, având în vedereteorema de structură a grupurilor abeliene finite. Dar primele 4 grupuri au fiecare câte4 elemente şi în acest caz trebuie să distingem între cele două tipuri: grupul 4Z şi

2 2Z Z , ultimul fiind cunoscut sub numele de grupul lui Klein. Numai al doilea esteizomorf cu grupul lui Klein, deoarece toate cele 4 puncte ale grupului sunt, fiecare,propriul său opus.

De remarcat marea diversitate a grupurilor obţinute, atât ca ordin al grupuluicât şi ca tip. Această diversitate creşte enorm o dată cu numărul elementelor corpuluiF. De aceea curbele eliptice sunt utile în proiectarea sistemelor criptografice.

9.9. TEME PENTRU CASĂ9.9.1. Să se determine curbele eliptice având coeficienţii în corpul Z5 şi să sedetermine grupurile corespunzătoare

Indicaţie şi răspuns

Pentru corpurile de caracteristică strict mai mare decât 3, cum este 5Z , ecuaţia

generală a curbelor eliptice este: 2 3y x ax b . Sunt deci 25 de ecuaţii, din caretrebuie eliminate cele pentru care membrul drept are rădăcini multiple. Vom atribuilui a succesiv valorile: 0, ±1, ±2.

Page 21: CURBE ELIPTICE

Dacă 0a , atunci singura valoare a lui b pentru care polinomul în x arerădăcini multiple este 0b . Excluzând-o pe aceasta, obţinem 4 curbe eliptice:

2 3 2 31; 2y x y x .

Dacă 1a , derivata polinomului din membrul drept este 23 1x care nuare rădăcini în 5Z şi deci oricare ar fi b acest polinom nu are rădăcini multiple. Deci,

obţinem zece ecuaţii de curbe eliptice: 2 3 ;y x x 2 3 1;y x x 2 3 2y x x .

Dacă 2a , derivata este 23 2x , care are rădăcinile: 1x , dacă2a şi 2x , dacă 2a . Înlocuind aceste rădăcini în polinomul din dreapta

pentru 2a , el devine: 1 2 b , care se anulează pentru 2b . Deci, pentru2a rămân numai trei ecuaţii de curbe eliptice: 2 3 2 32 ; 2 1y x x y x x .

Pentru 2a polinomul din dreapta devine: 3 1 b , care se anulează respectivpentru 1b . Deci, pentru 2a , obţinem încă trei ecuaţii de curbe eliptice:

2 3 2 32 ; 2 2y x x y x x .S-au obţinut deci 20 de ecuaţii de curbe eliptice. Următorul tabel precizează

grupurile acestor curbe.

Nr. Ecuaţia curbei Punctele curbei Grupulcurbei

1 2 3 1y x O; (0,1); (0,–1); (–1,0); (2,2); (2,–2) 6Z2 2 3 1y x O; (0,2); (0,–2); (1,0); (–2,1); (–2,–1) 6Z3 2 3 2y x O; (–1,1); (–1,–1); (2,0); (–2,2); (–2,–2) 6Z4 2 3 2y x O; (1,2); (1,–2); (2,1); (2,–1); (–2,0) 6Z5 2 3y x x O; (0,0); (2,0); (–2,0) 2 2Z Z

6 2 3y x x O; (0,0); (1,0); (–1,0); (2,1); (2,–1);(–2,2); (–2,–2) 2 4Z Z

7 2 3 1y x x O; (0,1); (0,–1);(–1,2); (–1,–2); (2,1);(2,–1); (–2,1); (–2,–1) 9Z

8 2 3 1y x x O; (0,2); (0,-2);(1,1); (1,–1); (2,2);(2,–2); (–2,2); (–2,–2) 9Z

9 2 3 1y x x O; (0,1); (0,-1);(1,1); (1,–1); (–1,2);(–1,–2); (–2,0) 8Z

10 2 3 \ 1y x x O; (0,2); (0,–2);(1,2); (1,–2);(–1,2); (–1,–2); (2,0) 8Z

11 2 3 2y x x O; (1,2); (1,–2); (–1,0) 4Z12 2 3 2y x x O; (1,0); (–1,1); (–1,–1) 4Z13 2 3 2y x x O; (–2,1); (–2,–1) 3Z14 2 3 2y x x O; (2,2); (2,–2) 3Z15 2 3 2y x x O; (0,0) 2Z

Page 22: CURBE ELIPTICE

16 2 3 2y x x O; (0,0); (1,2); (1,–2); (–2,1); (–2,–1) 6Z17 2 3 2 1y x x O; (0,1); (0,–1);(1,2); (1,–2); (–2,2); (–2,–2) 7Z18 2 3 2 1y x x O; (0,2); (0,–2);(–1,1); –1,–1); (2,1); (2,–1) 7Z19 2 3 2 2y x x O; (1,1); (1,-1); (2,1); (2,-1) 5Z20 2 3 2 2y x x O; (–1,2); (–1,–2); (–2,2); (–2,–2) 5Z

Exemplificăm pentru prima curbă din tabel felul cum se obţin punctele curbei.Mai întâi precizăm că elementele lui 5Z care au rădăcini pătrate sunt: 0, 1 şi –1.

Primul are o singură rădăcină pătrată, al doilea are rădăcinile pătrate ±1, iar altreilea are rădăcinile pătrate ±2. Elementele ±2 nu au rădăcini pătrate, deci ecuaţiile

2 2y nu au soluţii.

Pentru 0x ecuaţia 2 3 1y x devine: 2 1y , care are rădăcinile ±1,deci se obţin punctele (0,1) şi (0,–1) care, potrivit convenţiei, sunt opuse unul altuia:(0,1) + (0,–1) = O.

Pentru 1x ecuaţia devine 2 2y care nu are rădăcini.

Pentru 1x ecuaţia devine: 2 0y care are o singură rădăcină, 0y , şise obţine punctual (–1,0) care este propriul său opus: (–1,0) + (–1,0) = O.

Pentru 2x ecuaţia devine 2 4y care are rădăcinile ±2, de unde se obţinpunctele (2,2) şi (2,–2) care sunt opuse unul altuia.

Pentru 2x ecuaţia devine 2 2y care nu are rădăcini.Aşadar, curba are 6 puncte: cele 5 menţionate mai înainte împreună cu punctul

O de la infinit. Potrivit teoremei de structură a grupurilor abeliene finite, dacă ordinulgrupului nu este divizibil prin pătrate (cum este cazul lui 6), atunci grupul este ciclic,deci grupul primei curbe din tabel este izomorf cu 6Z .

Curbele 1-4 şi 13-20 din tabel, având ca ordin numere nedivizibile cu pătrate,sunt ciclice.

În cazul când grupul este ciclic, cum este primul din tabel, ne interesează săgăsim un generator al acestuia. Pentru a stabili dacă punctul (0,1) este generator îladunăm cu el însuşi până obţinem ca rezultat opusul său, adică (0,–1).

Pentru a găsi coordonatele 3x şi 3y ale punctului (0,1) + (0,1) = 2·(0,1) se

folosesc formulele:

221

3 11

3 22

x ax xy

şi 21

3 1 3 11

32

x ay y x xy

în

care 1 0x şi 1 1y şi 0a . Se obţine: 3 0x şi 3 1y , adică tocmai opusullui (0,1). Deci 2·(0,1) = –(0,1), de unde rezultă 3·(0,1) = O, adică ordinul lui (0,1) este3 şi deci acest punct nu este generator.

Pornind cu punctul (2,2), adică luând în aceste formule 1 1 2x y şi 0a ,se obţine: 3 34 4 0, 2 3( 2) 1x y , deci s-a obţinut punctul (0,–1)care nu este opusul lui (2,2). Putem spune că ordinul acestui punct este strict mai maredecât 3 (şi divizor al lui 6), deci acest punct este un generator.

Page 23: CURBE ELIPTICE

Pentru a afla punctul 3·(2,2) = 2·(2,2) + (2,2) = (0,–1) + (2,2) se folosesc

formulele:2

2 13 1 2

2 1

y yx x xx x

şi 2 13 1 3 1

2 1

y yy y x xx x

, în care

1 0x , 1 1y , 2 2 2x y .

Se obţine: 213 3 2 2 1x , 1

3 1 3 2 ( 1) 0y , adică punctul(–1,0), ceea ce era de aşteptat pentru că acesta este singurul punct nenul care estepropriul să opus.

Pentru curbele 5-12 din tabel trebuie să stabilim dacă sunt sau nu ciclice.Grupul curbei 5 nu este ciclic, deoarece toate cele trei elemente nenule sunt

fiecare propriul său opus, deci au ordinul doi. Rezultă că acest grup este izomorf cugrupul lui Klein, 2 2Z Z . Grupurile de la curbele 11 şi 12 au tot4 elemente fiecare, dar elementele nenule ale acestora nu au toate ordinul doi, deciaceste grupuri sunt ciclice, izomorfe cu 4Z .

Grupurile curbelor 6, 9 şi 10 au fiecare 8 elemente, deci fiecare din acestegrupuri este de una din formele: 2 2 2Z Z Z , 2 4Z Z sau 8Z . Primul are toateelementele nenule de ordinul doi, al doilea are doar 4 şi ultimul are un singur elementde ordinul doi. Aşadar grupul curbei 6 este izomorf cu 2 4Z Z , iar celelalte douăsunt izomorfe cu 2Z .

Au rămas grupurile 7 şi 8 care au fiecare câte 9 elemente, deci un astfel degrup este sau ciclic, adică izomorf cu 9Z sau este izomorf cu 3 3Z Z . Calculândordinul diverselor elemente aşa cum s-a arătat mai sus, se deduce că amândouă acestegrupuri sunt ciclice.

Bibliografie[1] C. DOCHIŢOIU, Instrumente algebrice ale criptografiei, Editura ATM,Bucureşti, 2009.[2] N. KOBLITZ, A Course in Number Theory and Cryptography, Editura Springer,Berlin, 1988[3], by A. MENEZES, P. van OORSCHOT, and S. VANSTONE, Handbook ofApplied Cryptography, CRC Press, 1996.