Algorithmic Number Theory

1. Front Matter

   PDF

2. Shimura curve computations

   • Noam D. Elkies

   Pages 1-47

3. The Decision Diffie-Hellman problem

   • Dan Boneh

   Pages 48-63

4. Parallel implementation of Schönhage's integer GCD algorithm

   • Giovanni Cesari

   Pages 64-76

5. The complete analysis of the binary Euclidean algorithm

   • Brigitte Vallée

   Pages 77-94

6. Cyclotomy primality proving — Recent developments

   • Preda MihĂilescu

   Pages 95-110

7. Primality proving using elliptic curves: An update

   • F. Morain

   Pages 111-127

8. Bounding smooth integers (extended abstract)

   • Daniel J. Bernstein

   Pages 128-130

9. Factorization of the numbers of the form m ³ + c ₂ m ² + c ₁ m + c ₀

   • Zhang Mingzhi

   Pages 131-136

10. Modelling the yield of number field sieve polynomials

    • Brian Murphy

    Pages 137-150

11. A Montgomery-like square root for the Number Field Sieve

    • Phong Nguyen

    Pages 151-168

12. Robert Bennion's “hopping sieve”

    • William F. Galway

    Pages 169-178

13. Trading time for space in prime number sieves

    • Jonathan P. Sorenson

    Pages 179-195

14. Do sums of 4 biquadrates have a positive density?

    • Jean -Marc Deshouillers, FranÇois Hennecart, Bernard Landreau

    Pages 196-203

15. New experimental results concerning the Goldbach conjecture

    • J. -M. Deshouillers, H. J. J. te Riele, Y. Saouter

    Pages 204-215

16. Dense admissible sets

    • Daniel M. Gordon, Gene Rodemich

    Pages 216-225

17. An analytic approach to smooth polynomials over finite fields

    • Daniel Panario, Xavier Gourdon, Philippe Flajolet

    Pages 226-236

18. Generating a product of three primes with an unknown factorization

    • Dan Boneh, Jeremy Horwitz

    Pages 237-251

19. On the performance of signature schemes based on elliptic curves

    • Erik De Win, Serge Mister, Bart Preneel, Michael Wiener

    Pages 252-266

20. NTRU: A ring-based public key cryptosystem

    • Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman

    Pages 267-288

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.

• Analysis
• Prime
• Prime number
• Public Key
• algorithm
• algorithms
• communication
• cryptography
• finite field
• linear algebra
• number theory
• algorithm analysis and problem complexity

Policies and ethics