Constitutes the proceedings of the 5th International Algorithmic Number Theory Symposium, held in Australia in 2002. The 39 papers cover number theory, arithmetic geometry, elliptic curves and CM, point counting, cryptography, function fields, discrete logarithms, Groebner bases and more.

TheAlgorithmicNumberTheorySymposiabeganin1994atCornellUniversity inIthaca,NewYorktorecognizethegrowingimportanceofalgorithmicwork in the theory of numbers. The subject of the conference is broadly construed toencompassadiversebodyofmathematics,andtocoverboththetheoretical andpracticaladvancesinthe?eld. Theyhavebeenheldeverytwoyearssince: inBordeaux(Universit'eBordeauxI)in1996,Portland(ReedCollege)in1998, Leiden(UniversiteitLeiden)in2000,andthepresentconferencehostedbythe MagmaComputationalAlgebraGroupattheUniversityofSydney. TheconferenceprogramincludedinvitedtalksbyManjulBhargava(Prin- ton),JohnCoates(Cambridge),AntoineJoux(DCSSICryptoLab),BjornP- nen(Berkeley),andTakakazuSatoh(Saitama),aswellas34contributedtalks invariousareasofnumbertheory. Inadditiontothemathematicalprogram,the conferenceincludedaspecialdinnertohonourAlfvanderPoortenofMacquarie University,ontheoccasionofhis60thbirthday. Eachpaperwasreviewedbyatleasttwoexpertsexternaltotheprogram committeeandtheselectionofpaperswasmadeonthebasisoftheserec- mendations. Weexpressourappreciationtothe66expertrefereeswhoprovided reportsonaverytightschedule. Refereeingofthesubmissionfromamemberof theMagmagroupwasorganizedbyJoeBuhler. Theprogramcommitteethanksthegenerousadvicefromorganizersofpre- ousANTSconferences,particularlyJoeBuhler,WiebBosma,HendrikLenstra, andBartdeSmit. TheconferencewasgenerouslysupportedbytheCollegeof ScienceandTechnology,theSchoolofMathematicsandStatistics(bothatthe UniversityofSydney),theAustralianDefenceScienceTechnologyOrganisation, andeSign. April2002 JohnCannon ClausFieker DavidKohel TableofContents InvitedTalks GaussCompositionandGeneralizations ...1 ManjulBhargava EllipticCurves-TheCrossroadsofTheoryandComputation...9 JohnCoates TheWeilandTatePairingsasBuildingBlocks forPublicKeyCryptosystems...20 AntoineJoux UsingEllipticCurvesofRankOnetowardstheUndecidability ofHilbert'sTenthProblemoverRingsofAlgebraicIntegers...33 BjornPoonen Onp-adicPointCountingAlgorithmsforEllipticCurves overFiniteFields...43 TakakazuSatoh NumberTheory OnArithmeticallyEquivalentNumberFieldsofSmallDegree ...67 WiebBosma,BartdeSmit ASurveyofDiscriminantCounting...80 HenriCohen,FranciscoDiazyDiaz,MichelOlivier AHigher-RankMersenneProblem...95 GrahamEverest,PeterRogers,ThomasWard AnApplicationofSiegelModularFunctions toKronecker'sLimitFormula...108 TakashiFukuda,KeiichiKomatsu ComputationalAspectsofNUCOMP...1 20 MichaelJ. Jacobson,Jr. ,AlfredJ. vanderPoorten E?cientComputationofClassNumbersofRealAbelianNumberFields. . 134 St'ephaneR. Louboutin AnAcceleratedBuchmannAlgorithmforRegulatorComputation inRealQuadraticFields...148 UlrichVollmer VIII TableofContents ArithmeticGeometry SomeGenus3CurveswithManyPoints ...163 RolandAuer,JaapTop 7 8 Trinomialsax +bx+candax +bx+c withGaloisGroupsofOrder168and8*168...172 NilsBruin,NoamD. Elkies ComputationsonModularJacobianSurfaces...189 EnriqueGonz'alez-Jim'enez,JosepGonz'TheAlgorithmicNumberTheorySymposiabeganin1994atCornellUniversity inIthaca,NewYorktorecognizethegrowingimportanceofalgorithmicwork in the theory of numbers. The subject of the conference is broadly construed toencompassadiversebodyofmathematics,andtocoverboththetheoretical andpracticaladvancesinthe?eld. Theyhavebeenheldeverytwoyearssince: inBordeaux(Universit'eBordeauxI)in1996,Portland(ReedCollege)in1998, Leiden(UniversiteitLeiden)in2000,andthepresentconferencehostedbythe MagmaComputationalAlgebraGroupattheUniversityofSydney. TheconferenceprogramincludedinvitedtalksbyManjulBhargava(Prin- ton),JohnCoates(Cambridge),AntoineJoux(DCSSICryptoLab),BjornP- nen(Berkeley),andTakakazuSatoh(Saitama),aswellas34contributedtalks invariousareasofnumbertheory. Inadditiontothemathematicalprogram,the conferenceincludedaspecialdinnertohonourAlfvanderPoortenofMacquarie University,ontheoccasionofhis60thbirthday. Eachpaperwasreviewedbyatleasttwoexpertsexternaltotheprogram committeeandtheselectionofpaperswasmadeonthebasisoftheserec- mendations. Weexpressourappreciationtothe66expertrefereeswhoprovided reportsonaverytightschedule. Refereeingofthesubmissionfromamemberof theMagmagroupwasorganizedbyJoeBuhler. Theprogramcommitteethanksthegenerousadvicefromorganizersofpre- ousANTSconferences,particularlyJoeBuhler,WiebBosma,HendrikLenstra, andBartdeSmit. TheconferencewasgenerouslysupportedbytheCollegeof ScienceandTechnology,theSchoolofMathematicsandStatistics(bothatthe UniversityofSydney),theAustralianDefenceScienceTechnologyOrganisation, andeSign. April2002 JohnCannon ClausFieker DavidKohel TableofContents InvitedTalks GaussCompositionandGeneralizations ...1 ManjulBhargava EllipticCurves-TheCrossroadsofTheoryandComputation...9 JohnCoates TheWeilandTatePairingsasBuildingBlocks forPublicKeyCryptosystems...20 AntoineJoux UsingEllipticCurvesofRankOnetowardstheUndecidability ofHilbert'sTenthProblemoverRingsofAlgebraicIntegers...33 BjornPoonen Onp-adicPointCountingAlgorithmsforEllipticCurves overFiniteFields...43 TakakazuSatoh NumberTheory OnArithmeticallyEquivalentNumberFieldsofSmallDegree ...67 WiebBosma,BartdeSmit ASurveyofDiscriminantCounting...80 HenriCohen,FranciscoDiazyDiaz,MichelOlivier AHigher-RankMersenneProblem...95 GrahamEverest,PeterRogers,ThomasWard AnApplicationofSiegelModularFunctions toKronecker'sLimitFormula...108 TakashiFukuda,KeiichiKomatsu ComputationalAspectsofNUCOMP...120 MichaelJ. Jacobson,Jr. ,AlfredJ. vanderPoorten E?cientComputationofClassNumbersofRealAbelianNumberFields. . 134 St'ephaneR. Louboutin AnAcceleratedBuchmannAlgorithmforRegulatorComputation inRealQuadraticFields...148 UlrichVollmer VIII TableofContents ArithmeticGeometry SomeGenus3CurveswithManyPoints ...163 RolandAuer,JaapTop 7 8 Trinomialsax +bx+candax +bx+c withGaloisGroupsofOrder168and8*168...172 NilsBruin,NoamD. Elkies ComputationsonModularJacobianSurfaces...1 89 EnriqueGonz'alez-Jim'enez,JosepGonz'alez,JordiGu'ardia IntegralPointsonPuncturedAbelianSurfaces...198 AndrewKresch,YuriTschinkel Genus2Curveswith(3,3)-SplitJacobian andLargeAutomorphismGroup...205 TonyShaska TransportableModularSymbolsandtheIntersectionPairing...219 HelenaA. Verrill EllipticCurvesandCM ActionofModularCorrespondencesaroundCMPoints...234 Jean-MarcCouveignes,ThierryHenocq 2 3 CurvesDy =x ?xofOddAnalyticRank...244 NoamD. Elkies ComparingInvariantsforClassFieldsofImaginaryQuadraticFields...252 AndreasEnge,Fran,coisMorain ADatabaseofEllipticCurves-FirstReport...267 WilliamA. Stein,MarkWatkins PointCounting IsogenyVolcanoesandtheSEAAlgorithm...276 MireilleFouquet,Fran,coisMorain FastEllipticCurvePointCountingUsingGaussianNormalBasis...292 HaeYoungKim,JungYoulPark,JungHeeCheon,JeHongPark, JaeHeonKim,SangGeunHahn AnExtensionofKedlaya'sAlgorithmtoArtin-SchreierCurves inCharacteristic2...308 JanDenef,FrederikVercauteren TableofContents IX Cryptography ImplementingtheTatePairing ...324 StevenD. Galbraith,KeithHarrison,DavidSoldera SmoothOrdersandCryptographicApplications...338 CarlPomerance,IgorE. Shparlinski ChineseRemainderingforAlgebraicNumbersinaHiddenField...3 49 IgorE. Shparlinski,RonSteinfeld FunctionFields AnAlgorithmforComputingWeierstrassPoints...357 FlorianHess NewOptimalTameTowersofFunctionFieldsoverSmallFiniteFields ...372 Wen-ChingW. Li,HirenMaharaj,HenningStichtenoth, NoamD. Elkies PeriodicContinuedFractionsinEllipticFunctionFields...390 AlfredJ. vanderPoorten,XuanChuongTran DiscreteLogarithmsandFactoring FixedPointsandTwo-CyclesoftheDiscreteLogarithm ...405 JoshuaHolden RandomCayleyDigraphsandtheDiscreteLogarithm...416 JeremyHorwitz,RamarathnamVenkatesan TheFunctionFieldSieveIsQuiteSpecial...431 AntoineJoux,ReynaldLercier MPQSwithThreeLargePrimes...446 PaulLeyland,ArjenLenstra,BruceDodson,AlecMu?ett,SamWagsta? AnImprovedBabyStepGiantStepAlgorithm forPointCountingofHyperellipticCurvesoverFiniteFields...461 KazutoMatsuo,JinhuiChao,ShigeoTsujii 2 FactoringN=pq withtheEllipticCurveMethod...475 PeterEbinger,EdlynTeske GrobnerBases ANewSchemeforComputingwithAlgebraicallyClosedFields...491 AllanSteel X TableofContents Complexity AdditiveComplexityandRootsofPolynomials overNumberFieldsandp-adicFields...506 J. MauriceRojas AuthorIndex...5 17 Gauss Composition and Generalizations ManjulBhargava Clay Mathematics Institute and Princeton University Abstract. We discuss several higher analogues of Gauss composition and consider their potential algorithmic applications.