This book constitutes the refereed proceedings of the Third International Symposium on Algorithmic Number Theory, ANTS-III, held in Portland, Oregon, USA, in June 1998.
The volume presents 46 revised full papers together with two invited surveys. The papers are organized in chapters on gcd algorithms, primality, factoring, sieving, analytic number theory, cryptography, linear algebra and lattices, series and sums, algebraic number fields, class groups and fields, curves, and function fields.
Author(s): Noam D. Elkies (auth.), Joe P. Buhler (eds.)
Series: Lecture Notes in Computer Science 1423
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1998
Language: English
Pages: 646
Tags: Symbolic and Algebraic Manipulation; Algorithm Analysis and Problem Complexity; Data Encryption; Algorithms; Number Theory
Shimura curve computations....Pages 1-47
The Decision Diffie-Hellman problem....Pages 48-63
Parallel implementation of Schönhage's integer GCD algorithm....Pages 64-76
The complete analysis of the binary Euclidean algorithm....Pages 77-94
Cyclotomy primality proving — Recent developments....Pages 95-110
Primality proving using elliptic curves: An update....Pages 111-127
Bounding smooth integers (extended abstract)....Pages 128-130
Factorization of the numbers of the form m 3 + c 2 m 2 + c 1 m + c 0 ....Pages 131-136
Modelling the yield of number field sieve polynomials....Pages 137-150
A Montgomery-like square root for the Number Field Sieve....Pages 151-168
Robert Bennion's “hopping sieve”....Pages 169-178
Trading time for space in prime number sieves....Pages 179-195
Do sums of 4 biquadrates have a positive density?....Pages 196-203
New experimental results concerning the Goldbach conjecture....Pages 204-215
Dense admissible sets....Pages 216-225
An analytic approach to smooth polynomials over finite fields....Pages 226-236
Generating a product of three primes with an unknown factorization....Pages 237-251
On the performance of signature schemes based on elliptic curves....Pages 252-266
NTRU: A ring-based public key cryptosystem....Pages 267-288
Finding length-3 positive Cunningham chains and their cryptographic significance....Pages 289-298
Reducing ideal arithmetic to linear algebra problems....Pages 299-310
Evaluation of linear relations between vectors of a lattice in euclidean space....Pages 311-322
An efficient parallel block-reduction algorithm....Pages 323-337
Fast multiprecision evaluation of series of rational numbers....Pages 338-350
A problem concerning a character sum....Pages 351-357
Formal power series and their continued fraction expansion....Pages 358-371
Imprimitive octic fields with small discriminants....Pages 372-380
A table of totally complex number fields of small discriminants....Pages 381-391
Generating arithmetically equivalent number fields with elliptic curves....Pages 392-399
Computing the lead term of an abelian L -function....Pages 400-411
Timing analysis of targeted hunter searches....Pages 412-423
On successive minima of rings of algebraic integers....Pages 424-432
Computation of relative quadratic class groups....Pages 433-440
Generating class fields using Shimura reciprocity....Pages 441-453
Irregularity of prime numbers over real quadratic fields....Pages 454-462
Experimental results on class groups of real quadratic fields....Pages 463-474
Computation of relative class numbers of imaginary cyclic fields of 2-power degrees....Pages 475-481
Formal groups, elliptic curves, and some theorems of Couveignes....Pages 482-501
A comparison of direct and indirect methods for computing Selmer groups of an elliptic curve....Pages 502-513
An algorithm for approximate counting of points on algebraic sets over finite fields....Pages 514-527
S -integral points on elliptic curves and Fermat's triple equations....Pages 528-540
Speeding up Pollard's rho method for computing discrete logarithms....Pages 541-554
A general method of constructing global function fields with many rational places....Pages 555-566
Lattice basis reduction in function fields....Pages 567-575
Comparing real and imaginary arithmetics for divisor class groups of hyperelliptic curves....Pages 576-591
Unit computation in purely cubic function fields of unit rank 1....Pages 592-606
An improved method of computing the regulator of a real quadratic function field....Pages 607-620
The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2....Pages 621-638
