From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Factoring Bibliography
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
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"
Newsgroups: sci.math