Lecture Notes in Computer Science 6197 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Guillaume Hanrot François Morain Emmanuel Thomé (Eds.) Algorithmic Number Theory 9th International Symposium, ANTS-IX Nancy, France, July 19-23, 2010 Proceedings 1 3 VolumeEditors GuillaumeHanrot LIP/ENS-Lyon,46,alléed’Italie 69364LyonCedex07,France E-mail:[email protected] FrançoisMorain LIX/Écolepolytechnique 91128PalaiseauCedex,France E-mail:[email protected] EmmanuelThomé INRIANancy,projetCARAMEL 615ruedujardinbotanique 54602Villers-lès-NancyCedex,France E-mail:[email protected] LibraryofCongressControlNumber:2010930653 CRSubjectClassification(1998):F.2,G.2,E.3,I.1 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-642-14517-5SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-14517-9SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper 06/3180 Preface ANTS-IX was the ninth edition of the biennial International Symposium on Algorithmic Number Theory. The first edition of this symposium was held at Cornell University in 1994. ANTS-IX was held July 19-23, 2010 at INRIA in Nancy, France. The ANTS-IX Program Committee consisted of 12 members whose names are listed on the next page. The selection of the accepted papers among the submissionswasmadefrommid-Januaryto endofMarch2010.Eachpaperwas thoroughly reviewed by at least two experts, including a Program Committee member. The Program Committee selected 25 high-quality articles, which are excellent representatives of the current state of the art in various areas of al- gorithmic number theory. The Selfridge Prize in computational number theory was awardedto the authors of the best contributed paper presented at the con- ference. We gratefully thank the authors of all submitted papers for their hard work which made the selection of a varied program possible. We also thank the authorsof the acceptedpapers for their cooperationinthe timely productionof the revised versions. Each submitted paper was presented by one of its co-authors at the con- ference. Besides contributed papers, the conference included five invited talks by Henri Darmon (McGill University), Jean-Franc¸ois Mestre (Universit´e Paris 7), Gabriele Nebe (RWTH Aachen), CarlPomerance(Dartmouth College), and Oded Regev (Tel-Aviv University). We thank the invited speakers for having been able to provide abstracts of their talk, which are reproduced in this vol- ume. This list of invited speakers originally included Fritz Grunewald (HHU Du¨sseldorf), who unfortunately passed away on March 21, 2010, four months before the conference. A special lecture was held to honor his memory. Theconferenceorganizerswishto thankallthe people whomadethe confer- encepossible.Inparticular,wegratefullyacknowledgethesupportofthefunding institutions. May 2010 Guillaume Hanrot Franc¸ois Morain Emmanuel Thom´e Organization Organizing Committee Anne-Lise Charbonnier INRIA, Nancy, France J´er´emie Detrey INRIA, Nancy, France Pierrick Gaudry (Chair) CNRS, Nancy, France Emmanuel Thom´e INRIA, Nancy, France Paul Zimmermann INRIA, Nancy, France Program Committee Nigel Boston University of Wisconsin, USA John Cremona Warwick Mathematics Institute, UK Claus Fieker University of Sydney, Australia Guillaume Hanrot (PC Chair) E´cole Normale Sup´erieure, Lyon, France Kevin Hare University of Waterloo, Canada Thorsten Kleinjung E´cole Polytechnique F´ed´eralede Lausanne, Switzerland Kamal Khuri-Makdisi American University of Beirut, Lebanon Franc¸ois Morain (PC Chair) E´cole Polytechnique, France Takakazu Satoh Tokyo Institute of Technology, Japan Igor Shparlinski Macquarie University, Australia Alice Silverberg University of California at Irvine, USA Frederik Vercauteren Katholieke Universiteit Leuven, Belgium Poster Session Benjamin Smith INRIA Saclay, E´cole Polytechnique, France Sponsoring Institutions Institut National de Recherche en Informatique et Automatique (INRIA) Laboratoire Lorrain de Recherche en Informatique et Applications (LORIA) E´cole Polytechnique Centre National de la Recherche Scientifique (CNRS) Microsoft Research, USA Nancy Universit´e Groupement de Recherches en Informatique Math´ematique (GDR IM) Communaut´e Urbaine du Grand Nancy Conseil R´egionalde Lorraine VIII Organization Conference Website The names of the winners of the Selfridge Prize, material supplementing the contributed papers, and errata for the proceedings (if relevant), as well as the abstractsofthe postersandthe posterspresentedatANTS-IX,canbe foundat http://ants9.org/. Table of Contents Invited papers Putting the Hodge and Tate Conjectures to the Test ................. 1 Henri Darmon Curves of Genus 3 With a Group of Automorphisms Isomorphic to S ............................................................. 2 3 Jean-Franc¸ois Mestre Learning with Errors over Rings ................................... 3 Oded Regev Lattices and Spherical Designs..................................... 4 Gabriele Nebe Fixed Points for Discrete Logarithms ............................... 6 Mariana Levin, Carl Pomerance, and K. Soundararajan Contributed papers Explicit Coleman Integration for Hyperelliptic Curves ................ 16 Jennifer S. Balakrishnan, Robert W. Bradshaw, and Kiran S. Kedlaya Smallest Reduction Matrix of Binary Quadratic Forms: And Cryptographic Applications ....................................... 32 Aurore Bernard and Nicolas Gama Practical Improvements to Class Group and Regulator Computation of Real Quadratic Fields ............................................ 50 Jean-Franc¸ois Biasse and Michael J. Jacobson Jr. On the Use of the Negation Map in the Pollard Rho Method .......... 66 Joppe W. Bos, Thorsten Kleinjung, and Arjen K. Lenstra An O(M(n)logn) Algorithm for the Jacobi Symbol .................. 83 Richard P. Brent and Paul Zimmermann New Families of ECM Curves for Cunningham Numbers .............. 96 E´ric Brier and Christophe Clavier Visualizing Elements of Sha[3] in Genus 2 Jacobians.................. 110 Nils Bruin and Sander R. Dahmen X Table of Contents On Weil polynomials of K3 surfaces................................ 126 Andreas-Stephan Elsenhans and J¨org Jahnel Class Invariants by the CRT Method ............................... 142 Andreas Enge and Andrew V. Sutherland Short Bases of Lattices over Number Fields ......................... 157 Claus Fieker and Damien Stehl´e On the Complexity of the Montes Ideal Factorization Algorithm ....... 174 David Ford and Olga Veres Congruent Number Theta Coefficients to 1012 ....................... 186 William B. Hart, Gonzalo Tornar´ıa, and Mark Watkins Pairing the Volcano .............................................. 201 Sorina Ionica and Antoine Joux A Subexponential Algorithm for Evaluating Large Degree Isogenies .... 219 David Jao and Vladimir Soukharev Huff’s Model for Elliptic Curves ................................... 234 Marc Joye, Mehdi Tibouchi, and Damien Vergnaud Efficient Pairing Computation With Theta Functions ................. 251 David Lubicz and Damien Robert Small-Span Characteristic Polynomials of Integer Symmetric Matrices ........................................................ 270 James McKee Decomposition Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field ............................................... 285 Koh-ichi Nagao Factoring Polynomials over Local Fields II .......................... 301 Sebastian Pauli On a Problem of Hajdu and Tengely ............................... 316 Samir Siksek and Michael Stoll Sieving for Pseudosquares and Pseudocubes in Parallel Using Doubly-Focused Enumeration and Wheel Datastructures.............. 331 Jonathan P. Sorenson On the Extremality of an 80-Dimensional Lattice .................... 340 Damien Stehl´e and Mark Watkins Table of Contents XI Computing Automorphic Forms on Shimura Curves over Fields with Arbitrary Class Number .......................................... 357 John Voight Improved Primality Proving with Eisenstein Pseudocubes ............. 372 Kjell Wooding and H.C. Williams Hyperbolic Tessellations Associated to Bianchi Groups................ 385 Dan Yasaki Author Index.................................................. 397