CURBE ELIPTICE

download CURBE ELIPTICE

of 23

  • date post

    03-Jan-2016
  • Category

    Documents

  • view

    261
  • download

    1

Embed Size (px)

description

Fundamentele Algebrice Ale Informaticii

Transcript of CURBE ELIPTICE

  • MODULUL 9CURBE ELIPTICE

    Tema are ca scop prezentarea detaliat a curbelor eliptice, care stau la bazamultor aplicaii 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 multsiguran.

    Studenii vor ntocmi o tem de cas care const n rezolvarea problemelor iexerciiilor propuse. Cuvinte cheie: curb eliptic, adunarea punctelor unei curbe eliptice, ordin al unuigrup; ordin al unui element al unui grup.Indicaii de studiere a temei: Timpul minim pe care trebuie s-l acordai studieriiacestui modul este de 3 ore.Se citete cu atenie i se noteaz ideile principale, ecuaiile matematice, seaprofundeaz noiunile subliniate. Se apeleaz la literatura suplimentar indicat. Separcurg ntrebrile de control i testele de verificare. Se studiaz problemele iexerciiile rezolvate. Se rezolv exerciiile propuse. Dac nu se neleg rezolvrile saunu pot da soluii unor probleme propuse se restudiaz subiectul n cauz.

    Cuprins9.1 Definiii, notaii.9.2 Forme reduse ale ecuaiei unei curbe eliptice.9.3 Operaia de adunare a punctelor unei curbe eliptice.9.4 Metode generale pentru determinarea grupului unei curbe eliptice.9.5 Relaii 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 nsuirea acestei teme, studentul va cunoate: Forma general a ecuaiei unei curbe eliptice; Structura de grup a mulimii punctelor unei curbe eliptice; Curbe eliptice peste unele corpuri finite; Ordinul grupului unei curbe eliptice; Ordinul unui element al unei curbe eliptice;

  • 9.1 DEFINIII, NOTAIICurbele eliptice au fost puse n eviden de foarte mult vreme, ele furniznd

    obiecte remarcabile ale Geometriei algebrice. De dat mai recent, cam din 1985 s-aremarcat utilitatea lor n criptografie. Pn n prezent, au fost deja folosite n testareaprimalitii, n descompunerea n factori a numerelor mari, precum i n proiectareasistemelor criptografice.

    Pentru c ne intereseaz n primul rnd 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 definete printr-o ecuaie deforma:

    2 3 21 3 2 4 6y a xy a y x a x a x a , (1)n care coeficienii sunt elemente ale lui F. Se cere ca aceti coeficieni s fie astfelnct ecuaia s nu admit soluii singulare, adic perechi de elemente x i y ale lui Fcare s satisfac att ecuaia (1), ct i cele dou ecuaii obinute din aceasta prinderivare n raport cu x i cu y.

    n general, o pereche (x,y) de elemente ale lui F se mai numete 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 mulimea punctelor ale cror coordonate satisfac ecuaia(1), la care se adaug un simbol O numit punctul de la infinit. Dac un alt corp K lconine pe F, atunci se poate considera curb i peste corpul K i deci are sensmulimea ( )K . Firete, aceast mulime conine mulimea ( )F .

    9.2 FORME REDUSE ALE ECUAIEI UNEI CURBEELIPTICE

    O transformare a planului 2F n el nsui definit prin ecuaii de forma:1 1 1

    1 2 2 12 2 2

    ; 0x x yy x y

    (2)

    se numete transformare afin a planului.Evident c printr-o transformare afin ecuaia (1) a curbei se poate modifica i

    vom cuta acele transformri care conduc la ecuaii mai simple. De regul cndaplicm transformarea (2) ecuaiei (1), revenim la vechile notaii ale variabilelor,adic scriem din nou x n loc de x i y n loc de y . Spunem pe scurt c nlocuim necuaia (1) pe x cu 1 1 1x y i y cu 2 2 2x y Avem n vedereurmtoarele situaii:

    Cazul cnd caracteristica lui F este diferit de 2 i de 3nlocuind n ecuaia (1) pe y cu 1 312y a x a , din aceast ecuaie vor

    disprea termenii n xy i y astfel c ecuaia (1) va cpta forma:

  • 2 3 22 4 6y x a x a x a . (3)n acest caz putem da o formulare mai precis condiiei ca ecuaia (3) s nu

    aib puncte singulare, condiie cerut prin definiia curbei eliptice. Anume, sistemuldin care se obin punctele singulare este:

    2 3 22 4 62 2 43 2 0

    2 0

    y x a x a x ax a x ay

    (4)

    iar acest sistem are soluii dac i numai dac polinomul din membrul drept al ecuaiei(3) are rdcini multiple.

    Aadar n cazul cnd caracteristica lui F este diferit de 2 ecuaia (3) esteecuaia general a unei curbe eliptice, dac polinomul din membrul drept nu arerdcini comune cu derivata sa.

    Mai menionm c dac, n plus, caracteristica lui F este diferit nu numai de2, ci i de 3, atunci prin transformarea de nlocuire a lui x cu 23

    ax , n membruldrept al ecuaiei (3) va dispare termenul n 2x .

    Ca urmare, dac F are caracteristica diferit i de 2 i de 3, atunci ecuaiageneral a unei curbe eliptice este:

    2 3y x ax b , (5)n care coeficienii a i b trebuie s fie astfel nct polinomul din membrul drept s nuaib rdcini multiple.

    Cazul cnd caracteristica lui F este 2De ast dat dac n ecuaia (1) att 1a , ct i 3a sunt nuli, curba va avea

    puncte singulare. ntr-adevr, n acest caz ecuaia obinut prin derivarea ecuaiei (1)n raport cu y va fi verificat pentru orice x i y i sistemul din care se obin punctelesingulare devine:

    2 3 22 4 62 2 40 3 2

    y x a x a x ax a x a

    (6)

    care are soluii ntr-o extensie adecvat a corpului F. Aadar coeficienii 1a i 3a dinecuaia (1) nu pot fi amndoi nuli. Sunt posibile atunci urmtoarele dou subcazuri.Subcazul numit nesupersingular, n care a1 este diferit de zero

    n acest caz nlocuind pe x cu 31ax a n ecuaia (1) aceasta devine:3 2

    2 3 3 3 31 3 2 4 61 1 1 1a a a ay a y x a y x a x a x aa a a a

  • sau 2 3 21 2 4 6y a xy x a x a x a . n aceast ultim ecuaie nlocuind pe y cu31a y i pe x cu 21a x i mprind ecuaia cu 61a , aceasta capt forma:2 3 22 4 6y xy x a x a x a . nlocuind n aceast ultim ecuaie pe y cu

    4y a se obine urmtoarea form:2 3 2y xy x ax b , (7)

    care este forma general a ecuaiei unei curbe eliptice nesupersingulare. Este uor 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 ecuaia (1) capt forma:2 33 3; 0y a y x ax b a , (8)

    care este forma general a ecuaiei unei curbe eliptice supersingulare. Este uor deverificat c oricare ar fi coeficienii a i b i 3a nenul, curba nu poate avea punctesingulare.

    n concluzie, fr a pierde generalitatea, ne putem limita la urmtoarele formereduse ale ecuaiilor 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 rdcini multiple. Dac, n plus, F arecaracteristica diferit i de 3, atunci se poate considera 2 0a , adic forma redus aecuaiei 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 mulimi de curbe sunt disjuncte.

    9.3 OPERAIA DE ADUNARE A PUNCTELOR UNEICURBE ELIPTICE

    Pentru definirea operaiei de adunare pe mulimea ( )F trebuie menionatrolul convenional al punctului de la infinit notat cu O. Urmtoarele grupe de regulidefinesc aceast operaie.Reguli convenionale (n care intervine punctul O)

    I. Convenia elementului neutru.Pentru orice punct P al curbei, avem:

    O + P = P + O = P, (9)relaia fiind adevrat i pentru P = O. Aadar punctul O are rolul de element neutrual operaiei.

    II. Convenia elementului opus.

  • Dac 1x i 1y sunt coordonatele unui punct P O al curbei, atunci nlocuindn ecuaia curbei pe x cu 1x se obine o ecuaie de gradul doi n y, pentru care 1y esteuna din soluii. Fie 2y cealalt soluie. Notm P punctul avnd coordonatele 1x i2y . Cu aceast notaie postulm:

    P + (P) = (P) + P = O, (10)adic punctul notat P se comport n aceast operaie ca opusul lui P.

    Elementul 2y se poate preciza n funcie de forma redus a ecuaiei pe care ofolosim.

    - Dac folosim forma redus 2 3 22 4 6y x a x a x a (deci ncazul cnd caracteristica lui F este diferit de 2), atunci 2 1y y .

    - Dac folosim forma redus 2 3 2 ; 0y xy x ax b b (cnd Fare caracteristica 2 i curba este nesupersingular), atunci 1 2 1y y x i deci2 1 1y y x .

    - Dac folosim forma redus 2 33 3; 0y a y x ax b a (cndF are caracteristica doi i curba este supersingular), atunci 1 2 3y y a i deci2 1 3y y a .

    Remarcm faptul c dac dou puncte diferite de O ale curbei au aceeaiabscis, atunci ele sunt sau opuse unul altuia sau coincid. (Aceste situaii nu suntdisjuncte: de exemplu, dac ecuaia curbei este 2 3 22 4 6y x a x a x a i 1xeste o rdcin a polinomului din membrul drept, atunci punctul 1P de coordonate 1xi 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 convenia menionatpentru adunare. Aadar dac abscisele celor dou puncte ce urmeaz a se aduna suntegale, atunci vom considera numai situaia cnd cele dou puncte coincid.

    Pentru deducerea formulelor de adunare a punctelor diferite de O vor trebuifolosite pe rnd cele trei forme reduse ale ecuaiei curbei.

    Adunarea punctelor curbei cnd caracteristica lui f este diferit de 2Ecuaia 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 sdeterminm coordonatele 3x i 3y