From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Factoring Bibliography
Date: Fri, 22 Jan 1993 17:18:47 GMT
Factoring and Primality Testing Bibliography
--------------------------------------------
General References
------------------
(1) Knuth Vol. 2 Chapter 4
(2) David Bressoud
Factoring and Primality Testing
Springer-Verlag ISBN 0-387-97040-1 1990
This is the most recent book on the subject. It does not cover
the Cohen-Lenstra-Bosma algorithm or the Number Field Sieve.
It is quite good.
(3) Hans Riesel
Prime Numbers and Computer Methods for Factorization
Birkhauser ISBN 0-8176-3291-3 1985
(4) Brillhart, Lehmer, Selfridge, Tuckerman, & Wagstaff Jr.
Factorization of b^n +/-1 for b = 2,3,5,6,7,10,11,12 up
to high powers
Contemporary Mathematics Vol 22. American Math. Society
ISBN 0-8218-5078-4 (2nd ed.) 1987
This has an extensive bibliography.
Primality Testing
-----------------
(1) Probable prime methods
The subject is well-covered in Bressoud's and Riesel's books.
You should also read:
(a) Brillhart, Lehmer, & Selfridge
New Primality Criteria and factorizations of 2^n +/- 1.
Math. Comp. Vol 29 1975, pp 620-647
(b) Pomerance, Selfridge, & Wagstaff Jr.
The pseudoprimes to 25*10^9
Math. Comp. Vol 35 1980 pp. 1003-1026
(2) Lucas-Lehmer methods and extensions
(a) H.C. Williams & J.S. Judd
Determination of the primality of N by using factors of N^2 +/- 1
Math. Comp. Vol 30, 1976, pp 157-172
Some algorithms for prime testing using generalized Lehmer functions
Math. Comp. Vol 30, 1976 pp. 867-886
(b) H.C. Williams & R. Holte
Some observations on primality testing
Math. Comp. Vol 32, 1978, pp. 905-917
(3) Cohen-Lenstra-Bosma cyclotomic ring methods
(a) Adelman, Pomerance, & Rumely
On distinguishing prime numbers from composite numbers
Ann. of Math. Vol 117, 1983, pp. 173-206
(b) H. Cohen & A. Lenstra
Implementation of a new primality test
Math. Comp. Vol 48, 1987, pp. 103-121
(c) H. Cohen & H. Lenstra Jr.
Primality testing and Jacobi sums
Math. Comp. Vol 42, 1984, pp. 297-330
The most comprehensive work is: [N.B. 300 pages with lengthy bibliography]
(d) W. Bosma & M. van der Hulst
Primality Testing with Cyclotomy
Thesis, University of Amsterdam Press.
(4) Atkin-Morain-Goldwasser elliptic curve methods
The definitive work to date is:
(a) F. Morain
Implementation of the Goldwasser-Killian-Atkin primality testing algorithm
Report, University of Limoges, Project Algo, 1988
This too has an extensive bibliography.
Factoring
---------
(1) Pollard P+/-1 , Pollard Rho and Elliptic Curve Methods
The most comprehensive and best paper to date is:
(a) P. Montgomery
Speeding the Pollard and elliptic curve methods of factorization
Math. Comp. Vol. 48, 1987, pp. 243-265
See also
(b) P. Montgomery & R. Silverman
An FFT extension to the P-1 factoring algorithm
Math. Comp. Vol. 54, 1990, pp. 839-854
(c) P. Montgomery
An FFT extension of the elliptic curve method of factorization
Doctoral Dissertation, UCLA, 1992
(d) R. Silverman & S. Wagstaff Jr.
A practical analysis of the elliptic curve factoring algorithm
Math. Comp. (to appear July 1993)
(2) CFRAC
(a) J. Brillhart & M. Morrison
A Method of Factoring and the factorization of F7
Math. Comp. Vol 29, 1975 pp. 183-205
(3) Quadratic Sieve
(a) R. Silverman
The Multiple Polynomial Quadratic Sieve
Math. Comp. Vol 48, 1987, pp. 329-339
(b) T. Caron & R. Silverman
Parallel implementation of the quadratic sieve
J. Supercomputing, Vol. 1, 1988 pp. 273-290
(4) Number Field Sieve
(a) A. Lenstra, H. Lenstra Jr., M. Manasse, & J. Pollard
The Number Field Sieve
Proc. 1990 ACM STOC Conf.
(b) J. Buhler, H. Lenstra, & C. Pomerance
Factoring integers with the number field sieve
Preprint 1992
(5) Class Group & related methods
(a) C.P. Schnorr & H. Lenstra Jr.
A Monte-Carlo factoring algorithm with linear storage
Math. COmp. Vol 43, 1984, pp. 289-311
(b) D. Shanks
Class Number, A theory of factorization and genera
Proc. Symp. Pure Math. Vol 20 , 1970 pp 415-440
(6) Cyclotomic field methods
(a) E. Bach & J. Shallit
Factoring with Cyclotomic Polynomials
Math. Comp. Vol. 52, 1989, pp. 201-218
(7) General Approach
(a) J. Brillhart, P. Montgomery, & R. Silverman
Tables of factorizations of Fibonacci and Lucas Numbers
Math. Comp. Vol. 50, 1988, pp. 251-260
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"