FACTORIZATION WITH GENUS 2 CURVES亏格曲线分解

《FACTORIZATION WITH GENUS 2 CURVES亏格曲线分解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、MATHEMATICSOFCOMPUTATIONVolume00,Number0,Pages000{000S0025-5718(XX)0000-0FACTORIZATIONWITHGENUS2CURVESROMAINCOSSETAbstract.Theellipticcurvemethod(ECM)isoneofthebestfactorizationmethodsavailable.Itispossibletousehyperellipticcurvesinsteadofellipticcurvesbutitisintheo

2、ryslower.WeusespecialhyperellipticcurvesandKum-mersurfacestoreducethecomplexityofthealgorithm.OurimplementationGMP-HECMisfasterthanGMP-ECMforfactoringbignumbers.IntroductionTheellipticcurvemethod(ECM)introducedin1985byH.W.Lenstra,Jr.[6]playsanimportantroleinfactorin

3、gintegers.ECMisusedtondmediumsized"(upto60digits)primefactorsofrandom"numbers.Itisalsousedbyotherfac-toringalgorithmslikesievingmethodsforcofactoring[5].ECMisageneralizationofPollard'sp1algorithm:insteadofworkinginF,weworkinthegroupofppointsonanellipticcurve.We

4、generalizeitbyusinghyperellipticcurvesofgenus2insteadofellipticcurvesofgenus1.Atrstsightthehyperellipticcurvemethod"(HECM)seemsslowerthatECMbecauseoftworeasons:rstthearithmeticofhyperellipticcurvesisslowercom-paredtothearithmeticofellipticcurves,andsecondlyitspro

5、babilityofsuccessissmallerthanthatofECM.IndeedthisprobabilitydependsontheprobabilityofthecardinalityoftheJacobianofthecurvemoduloaprimefactorpofnbeingsmooth.Buttheprobabilityofanumberbeingsmoothdecreaseswithitssize.ByWeil'stheorem,thecardinalityofaJacobianofagenus2c

6、urveonFisaroundp2whereasthecardinalityofanpellipticcurveoverthesameeldisaroundp.ThisseemslikeamajordeterrenttousingHECM.ToavoiditweusespecialhyperellipticcurveswhoseJacobiansareisogenoustotheproductoftwoellipticcurves:theyarecalleddecomposable.OnerunofHECMwiththisk

7、indofcurvesisequivalenttotwosimultaneousrunsofECM,thustheprobabilityofsuccessofHECMwithdecomposablehyperellipticcurvesiscomparabletothatoftwoECM.Thecomplexityofstage1isdominatedbythecostofthearithmeticonthecurves.Ingenus1,thequickestarithmeticisobtainedbyusingMontgo

8、meryformul[8]orthenewEdwardscurves[1].Ingenus2,thebestknownformuluseKummersur-faces[3].TheKummersurfaceisavarietyobtainedbyidentifyingop