Bulletin of the American Mathematical Society

MathSciNet review: 1567658
Full text of review: PDF   This review is available free of charge.
Book Information:

Author: Hans Riesel
Title: Prime numbers and computer methods for factorization
Additional book information: Progress in Mathematics, vol. 57, Birkhäuser, Boston, Basel and Stuttgart, 1985, xvi + 464 pp., $44.95. ISBN 0-8176-3291-3.

Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975

H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103–121, S1–S4. MR 866102, DOI 10.1090/S0025-5718-1987-0866102-2

3.

S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th Annual ACM Symp. on Theory of Computing (1986), 316-329.

4.

J. C. Lagarias and A. M. Odlyzko, Computing π(x): an analytic method, J. Algorithms 8 (1987), 173-191.

5.

J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing π(x): the Meissel-Lehmer method, Math. Comp. 44 (1985), 537-560.

D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI 10.1017/s1446788700019364

7.

A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science (to appear).

8.

H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (to appear).

J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252

C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260

Carl Pomerance, The quadratic sieve factoring algorithm, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 169–182. MR 825590, DOI 10.1007/3-540-39757-4_{1}7

Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929

Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0

J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689

René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6

R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006

Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807

1.

L. M. Adleman, C. Pomerance and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. 117 (1983), 173-206. MR 0683806

2.

H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103-121. MR 866102

3.

S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th Annual ACM Symp. on Theory of Computing (1986), 316-329.

4.

J. C. Lagarias and A. M. Odlyzko, Computing π(x): an analytic method, J. Algorithms 8 (1987), 173-191.

5.

J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing π(x): the Meissel-Lehmer method, Math. Comp. 44 (1985), 537-560.

6.

D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), 508-510. MR 417032

7.

A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science (to appear).

8.

H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (to appear).

9.

J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521-528. MR 354514

10.

C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds. ), Math. Centre Tracts 154/155, Mathematisch Centrum, Amsterdam, 1982, pp. 89-139. MR 700260

11.

C. Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology (T. Beth, N. Cot and I. Ingemarsson, eds. ), Springer Lecture Notes in Computer Science 209 (1985), 169-182. MR 825590

12.

C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity (D. S. Johnson, T. Nishizeki, A. Nozaki and H. S. Wilf, eds. ), Academic Press, Orlando, Florida, 1987, pp. 119-143. MR 910929

13.

M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128-138. MR 566880

14.

J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 137689

15.

R. J. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494. MR 777280

16.

R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 84-85; erratum, ibid. 7 (1978), 118. MR 429721

17.

V. Strassen, Einige Resultate über Berechnungskomplexität, Jahresber. Deutsch. Math.-Verein 78 (1976/77), 1-8. MR 438807