This volume presents the refereed proceedings of the First Algorithmic Number Theory Symposium, ANTS-I, held at Cornell University, Ithaca, NY in May 1994.
The 35 papers accepted for inclusion in this book address many current issues of algorithmic, computational and complexity-theoretic aspects of number theory and thus report the state-of-the-art in this exciting area of research; the book also contributes essentially to foundational research in cryptology and coding.
Of particular value is a collection entitled "Open Problems in Number Theoretic Complexity, II" contributed by Len Adleman and Kevin McCurley. This survey presents on 32 pages 36 central open problems and relates them to the literature by means of some 160 references.
Author(s): W. R. Alford, Andrew Granville, Carl Pomerance (auth.), Leonard M. Adleman, Ming-Deh Huang (eds.)
Series: Lecture Notes in Computer Science 877
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1994
Language: English
Pages: 320
Tags: Symbolic and Algebraic Manipulation; Algorithm Analysis and Problem Complexity; Combinatorics; Data Encryption; Coding and Information Theory; Systems and Information Theory in Engineering
On the difficulty of finding reliable witnesses....Pages 1-16
Density computations for real quadratic 2-class groups....Pages 17-17
Lattice sieving and trial division....Pages 18-27
A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields....Pages 28-40
Computing rates of growth of division fields on CM Abelian varieties....Pages 41-41
Algorithms for CM-Fields....Pages 42-42
Schoof's algorithm and isogeny cycles....Pages 43-58
Integer points on rational elliptic curves....Pages 59-59
Counting the number of points on elliptic curves over finite fields of characteristic greater than three....Pages 60-70
Straight-line complexity and integer factorization....Pages 71-79
Decomposition of algebraic functions....Pages 80-92
A new modular interpolation algorithm for factoring multivariate polynomials....Pages 93-107
The function field sieve....Pages 108-121
Heegner point computations....Pages 122-133
Computing the degree of a modular parametrization....Pages 134-142
Galois representations from the cohomology of SL(3,ℤ)....Pages 143-143
An analysis of the Gaussian algorithm for lattice reduction....Pages 144-158
A fast variant of the Gaussian reduction algorithm....Pages 159-159
Reducing lattice bases by means of approximations....Pages 160-168
Analysis of a left-shift binary GCD algorithm....Pages 169-183
The complexity of greatest common divisor computations....Pages 184-193
Explicit formulas for units in certain quadratic number fields....Pages 194-208
Factorization of polynomials over finite fields in subexponential time under GRH....Pages 209-219
On orders of optimal normal basis generators....Pages 220-220
Computing in the jacobian of a plane algebraic curve....Pages 221-233
Under the assumption of the Generalized Riemann Hypothesis verifying the class number belongs to NP ∩ co-NP....Pages 234-247
Calculating the class number of certain Hilbert class fields....Pages 248-248
Efficient checking of computations in number theory....Pages 249-249
Constructing elliptic curves with given group order over large finite fields....Pages 250-263
Computing π(x), M(x) and Ψ(x)....Pages 264-264
On some applications of finitely generated semi-groups....Pages 265-279
Improved incremental prime number sieves....Pages 280-288
Polynomial time algorithms for discrete logarithms and factoring on a quantum computer....Pages 289-289
On dispersion and Markov constants....Pages 290-290
Open problems in number theoretic complexity, II....Pages 291-322
