This book constitutes the refereed proceedings of the 4th International Algorithmic Number Theory Symposium, ANTS-IV, held in Leiden, The Netherlands, in July 2000.
The book presents 36 contributed papers which have gone through a thorough round of reviewing, selection and revision. Also included are 4 invited survey papers. Among the topics addressed are gcd algorithms, primality, factoring, sieve methods, cryptography, linear algebra, lattices, algebraic number fields, class groups and fields, elliptic curves, polynomials, function fields, and power sums.
Author(s): Jin-Yi Cai (auth.), Wieb Bosma (eds.)
Series: Lecture Notes in Computer Science 1838
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2000
Language: English
Pages: 612
Tags: Algorithm Analysis and Problem Complexity; Symbolic and Algebraic Manipulation; Data Encryption; Number Theory; Discrete Mathematics in Computer Science
Front Matter....Pages -
The Complexity of Some Lattice Problems....Pages 1-32
Rational Points Near Curves and Small Nonzero | x 3 − y 2 | via Lattice Reduction....Pages 33-63
Coverings of Curves of Genus 2....Pages 65-84
Lattice Reduction in Cryptology: An Update....Pages 85-112
Construction of Secure C ab Curves Using Modular Curves....Pages 113-126
Curves over Finite Fields with Many Rational Points Obtained by Ray Class Field Extensions....Pages 127-134
New Results on Lattice Basis Reduction in Practice....Pages 135-152
Baby-Step Giant-Step Algorithms for Non-uniform Distributions....Pages 153-168
On Powers as Sums of Two Cubes....Pages 169-184
Factoring Polynomials over ρ -Adic Fields....Pages 185-208
Strategies in Filtering in the Number Field Sieve....Pages 209-231
Factoring Polynomials over Finite Fields and Stable Colorings of Tournaments....Pages 233-245
Computing Special Values of Partial Zeta Functions....Pages 247-256
Construction of Tables of Quartic Number Fields....Pages 257-268
Counting Discriminants of Number Fields of Degree up to Four....Pages 269-283
On Reconstruction of Algebraic Numbers....Pages 285-296
Dissecting a Sieve to Cut Its Need for Space....Pages 297-312
Counting Points on Hyperelliptic Curves over Finite Fields....Pages 313-332
Modular Forms for GL(3) and Galois Representations....Pages 333-346
Modular Symbols and Hecke Operators....Pages 347-357
Fast Jacobian Group Arithmetic on C ab Curves....Pages 359-376
Lifting Elliptic Curves and Solving the Elliptic Curve Discrete Logarithm Problem....Pages 377-384
A One Round Protocol for Tripartite Diffie–Hellman....Pages 385-393
On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields....Pages 395-404
Component Groups of Quotients of J 0 ( N )....Pages 405-412
Fast Computation of Relative Class Numbers of CM-Fields....Pages 413-422
On Probable Prime Testing and the Computation of Square Roots mod n ....Pages 423-437
Improving Group Law Algorithms for Jacobians of Hyperelliptic Curves....Pages 439-447
Central Values of Artin L -Functions for Quaternion Fields....Pages 449-458
The Pseudoprimes up to 10 13 ....Pages 459-473
Computing the Number of Goldbach Partitions up to 5 10 8 ....Pages 475-490
Numerical Verification of the Brumer-Stark Conjecture....Pages 491-503
Explicit Models of Genus 2 Curves with Split CM....Pages 505-513
Reduction in Purely Cubic Function Fields of Unit Rank One....Pages 515-532
Factorization in the Composition Algebras....Pages 533-537
A Fast Algorithm for Approximately Counting Smooth Numbers....Pages 539-549
Computing All Integer Solutions of a General Elliptic Equation....Pages 551-561
A Note on Shanks’s Chains of Primes....Pages 563-580
Asymptotically Fast Discrete Logarithms in Quadratic Number Fields....Pages 581-594
Asymptotically Fast GCD Computation in ℤ[ i ]....Pages 595-613
Back Matter....Pages -
