FINDING ELLIPTIC CURVES WITH A用椭圆曲线求椭圆曲线.pdf

《FINDING ELLIPTIC CURVES WITH A用椭圆曲线求椭圆曲线.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FINDINGELLIPTICCURVESWITHASUBGROUPOFPRESCRIBEDSIZEIGORE.SHPARLINSKIANDANDREWV.SUTHERLANDAbstract.AssumingtheGeneralizedRiemannHypothesis,wedesignadeterministicalgorithmthat,givenaprimepandpositiveintegerm=o(p1/2(logp)−4),outputsanellipticcurveEoverthefinitefieldFpforwhichthecar

2、dinalityofE(Fp)isdivisiblebym.Therunningtimeofthealgorithmismp1/2+o(1),andthisleadstomoreefficientconstructionsofrationalfunctionsoverFpwhoseimageissmallrelativetop.Wealsogiveanunconditionalversionofthealgorithmthatworksforalmostallprimesp,andgiveaprobabilisticalgorithmwithsube

3、xponentialtimecomplexity.1.Introduction1.1.Motivation.LetFqdenotethefinitefieldwithqelements.ForanellipticcurveE/Fq,wedenotebyE(Fq)thegroupofFq-rationalpointsonE,whichwerecallisafiniteabeliangroup;see[3,20,44]forbackgroundonellipticcurvesandbasicterminology.Wewishtoconsiderthepr

4、oblemofexplicitlyconstructinganellipticcurveE/Fqforwhich#E(Fq)≡0(modm),foragivenintegerm.ThisproblemnaturallyfallsintothecategoryofquestionsconcerningtheconstructionofellipticcurvesE/Fqforwhich#E(Fq)hasapre-arXiv:1403.7887v3[math.NT]29Nov2014scribedarithmeticstructure.Forexam

5、ple,motivatedbycryptographicapplications,manyauthorshaveconsideredtheproblemoffindingel-lipticcurvesoverfinitefieldsforwhich#E(Fq)isprime;see[41]foranefficientprobabilisticalgorithm,conditionalundertheGeneralizedRiemannHypothesis(GRH).Asecondmotivationcomesfromoneoftheclassicalque

6、stionsofthetheoryoffinitefields:constructingrationalfunctionswithasmallimagesetor,moregenerally,withmanyrepeatedvalues.Ithasbeenshownthatresultsofthistypeareofinterestforcertaincryptographic1991MathematicsSubjectClassification.11G07,11T06,11Y16.Keywordsandphrases.ellipticcurve,d

7、ivisibility,smoothnumbers,primequa-draticresidues.12IGORE.SHPARLINSKIANDANDREWV.SUTHERLANDattacks;see[9,10,11,24,25],forexample.Moreprecisely,foralgo-rithmsof[9,10,11,24,25]itisimportanttohaveapolynomialorarationalfunctionf∈Fq(X)ofprescribeddegree(orwiththedegreeinaprescribed

8、dyadicinterval)suchthatthemapf:Fq→Fqhasmany“collisions”,or,moreforma