Summation polynomials and the discrete logarithm problem on elliptic curves

  • 格式:pdf
  • 大小:88.32 KB
  • 文档页数:6

Summationpolynomialsandthediscretelogarithmproblemonellipticcurves

IgorSemaevDepartmentofMathematicsUniversityofLeuven,Celestijnenlaan200B3001Heverlee,BelgiumIgor.Semaev@wis.kuleuven.ac.be

February5,2004

AbstractTheaimofthepaperistheconstructionoftheindexcalculusalgo-rithmforthediscretelogarithmproblemonellipticcurves.Theconstruc-tionpresentedhereisbasedontheproblemoffindingboundedsolutionstosomeexplicitmodularmultivariatepolynomialequations.Theseequa-tionsarisefromtheellipticcurvesummationpolynomialsintroducedhereandmaybecomputedeasily.Roughlyspeaking,weshowthatgiventhealgorithmforsolvingsuchequations,whichworksinpolynomialorlowexponentialtimeinthesizeoftheinput,onefindsdiscretelogarithmsfasterthanbymeansofPollard’smethods.Keywords:ellipticcurves,summationpolynomials,thediscretelog-arithmproblem

1IntroductionLetEbetheellipticcurvedefinedovertheprimefinitefieldFpofpelementsbytheequation

Y2=X3+AX+B.(1)ThediscretelogproblemhereisgivenP,Q∈E(Fp)findanintegernumbernsuchthatQ=nPinE(Fp)ifsuchannexists.Itisofgreatimportanceincryptography,see[1]and[2].Theaimofthepaperistheconstructionoftheindexcalculusalgorithmfortheproblem.Theconstructionpresentedhereisbasedontheproblemoffindingboundedsolutionstosomeexplicitmodularmultivariatepolynomialequations.TheseequationsarisefromthesummationpolynomialsintroducedinthesecondSectionofthepaper.InthethirdSectionweshow,roughlyspeaking,thatgivenagoodalgorithmforsolvingsuchequationsonefindsdiscretelogarithmsinE(Fp)probablyfasterthanby

1meansofPollard’smethods,see[3],[4],[6]forthem.Anindexcalculusfortheproblem,calledthexendicalculus,waspublishedbySilverman[7].Itwasshownin[8]thatthexendicalculusfailstoimproveknownbounds.WestressherethattheunderlyingideaofthepresentnewapproachisdifferentfromSilverman’s.

2SummationPolynomialsLetEbetheellipticcurvegivenbytheequation(1)overafieldKofcharac-teristic=2,3,whichisnotnecessaryFpnow.Foranynaturalnumbern≥2weintroducethepolynomialfn=fn(X1,X2,...,Xn)innvariableswhichisrelatedtothearithmeticoperationonE.Wecallthispolynomialsummationpolynomialanddefineitbythefollowingproperty.Letx1,x2,...,xnbeanyel-ementsfromK,thealgebraicclosureofthefieldK,thenfn(x1,x2,...,xn)=0ifandonlyifthereexisty1,y2,...,yn∈Ksuchthatpoints(xi,yi)areonEand(x1,y1)+(x2,y2)+...+(xn,yn)=P∞inthegroupE(K).

Theorem1Thepolynomialfnmaybedefinedbyf2(X1,X2)=X1−X2,andf3(X1,X2,X3)=

(X1−X2)2X23−2((X1+X2)(X1X2+A)+2B)X3+((X1X2−A)2−4B(X1+X2)),andfn(X1,X2,...,Xn)=ResX(fn−k(X1,...,Xn−k−1,X),fk+2(Xn−k,...,Xn,X))(2)foranyn≥4andn−3≥k≥1.Thepolynomialfnissymmetricandofdegree2n−2ineachvariableXiforanyn≥3.Thepolynomialfnisabsolutelyirreducibleand

fn(X1,...,Xn−1,Xn)=f2n−1(X1,...,Xn−1)X2n−2n+...foranyn≥3.Proof.Firstwedefinethepolynomialfnforn=2andn=3.Oneseesthatf2=X1−X2.Nowwedeterminef3.Let(x1,y1)and(x2,y2)betwoaffinepointsonEsuchthatx1=x2.Wedenote

(x3,y3)=(x1,y1)+(x2,y2),(x4,y4)=(x1,y1)−(x2,y2).

Onecanseethatx3,x4arerootsofaquadraticpolynomial,whosecoefficientsaresymmetricfunctionsinx1andx2.Really,wederive

x3=λ23−(x1+x2),x4=λ24−(x1+x2),

2whereλ3=(y1−y2)/(x1−x2)andλ4=(y1+y2)/(x1−x2).Thenx3+x4=λ23+λ24−2(x1+x2)=2(x1+x2)(x1x2+A)+2B(x1−x2)2,

andx3x4=(λ23−(x1+x2))(λ24−(x1+x2))=(x1x2−A)2−4B(x1+x2)(x1−x2)2,

Thex-coordinatesx3andx4arerootsofthepolynomial(x1−x2)2X2−2((x1+x2)(x1x2+A)+2B)X+((x1x2−A)2−4B(x1+x2)).Ifx1=x2and(x3,y3)=2(x1,y1),where(x3,y3)isanaffinepointonE,onecanseethatx3istherootofthesamepolynomial.Itmeansthatonecantakef3(X1,X2,X3)=

(X1−X2)2X23−2((X1+X2)(X1X2+A)+2B)X3+((X1X2−A)2−4B(X1+X2)).Oneseesthatthepolynomialf3(X1,X2,X3)isirreducibleoverthefieldK(X3).

Itfollowsfromthefactthattheequationf3(X1,X2,X3)=0isisomorphicoverK(X3)totheinitialellipticcurve(1).Inparticular,thepolynomialf3(X1,X2,X3)isabsolutelyirreducible.Sowehaveprovedallclaimswhenn=3.Letn≥4,andn−3≥k≥1,and

(x1,y1)+(x2,y2)+...+(xn,yn)=P∞(3)inthegroupE(K).Firstweconsiderthecase(x1,y1)+...+(xn−k−1,yn−k−1)=(x,y)forsomeaffinepoint(x,y)∈E.So(xn−k,yn−k)+...+(xn,yn)=(x,−y).Itimpliesthepolynomialsfn−k(x1,...,xn−k−1,X)andfk+2(xn−k,...,xn,X)havenonzeroleadingcoefficientsandthecommonrootx.Itfollowsbyinductionthattheleadingcoefficientsofthepolynomialsaref2n−k−1(x1,...,xn−k−1)andf2k+1(xn−k,...,xn)whicharenonzero.Thenfn(x1,x2,...,xn)=

ResX(fn−k(x1,...,xn−k−1,X),fk+2(xn−k,...,xn,X))=0Let(x1,y1)+...+(xn−k−1,yn−k−1)=P∞then(xn−k,yn−k)+...+(xn,yn)=P∞andtheleadingcoefficientsofthepolynomialsfn−k(x1,...,xn−k−1,X)andfk+2(xn−k,...,xn,X)arezeros.Againfn(x1,x2,...,xn)=

ResX(fn−k(x1,...,xn−k−1,X),fk+2(xn−k,...,xn,X))=0.

3