From msuinfo!srvr1.engin.umich.edu!sol.ctr.columbia.edu!usc!howland.reston.ans.net!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs Fri Jan 22 16:43:06 1993
Newsgroups: sci.math,sci.crypt
Path: msuinfo!srvr1.engin.umich.edu!sol.ctr.columbia.edu!usc!howland.reston.ans.net!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs
From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Factoring Bibliography
Message-ID: <1993Jan22.171847.7298@linus.mitre.org>
Sender: news@linus.mitre.org (News Service)
Nntp-Posting-Host: gauss.mitre.org
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Fri, 22 Jan 1993 17:18:47 GMT
Lines: 168
Xref: msuinfo sci.math:38761 sci.crypt:13190

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"