home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18660 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  4.9 KB
  1. Xref: sparky sci.math:18660 sci.crypt:7098
  2. Newsgroups: sci.math,sci.crypt
  3. Path: sparky!uunet!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs
  4. From: bs@gauss.mitre.org (Robert D. Silverman)
  5. Subject: Factoring Bibliography
  6. Message-ID: <1993Jan22.171847.7298@linus.mitre.org>
  7. Sender: news@linus.mitre.org (News Service)
  8. Nntp-Posting-Host: gauss.mitre.org
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. Date: Fri, 22 Jan 1993 17:18:47 GMT
  11. Lines: 168
  12.  
  13.         Factoring and Primality Testing Bibliography
  14.         --------------------------------------------
  15.  
  16. General References
  17. ------------------
  18.  
  19. (1) Knuth Vol. 2 Chapter 4
  20.  
  21. (2) David Bressoud
  22.     Factoring and Primality Testing
  23.     Springer-Verlag ISBN 0-387-97040-1   1990
  24.  
  25. This is the most recent book on the subject. It does not cover
  26. the Cohen-Lenstra-Bosma algorithm or the Number Field Sieve.
  27. It is quite good.
  28.  
  29. (3) Hans Riesel
  30.     Prime Numbers and Computer Methods for Factorization
  31.     Birkhauser ISBN 0-8176-3291-3   1985
  32.  
  33.  
  34. (4) Brillhart, Lehmer, Selfridge, Tuckerman, & Wagstaff Jr.
  35.     Factorization of b^n +/-1 for b = 2,3,5,6,7,10,11,12 up
  36.     to high powers
  37.     Contemporary Mathematics Vol 22. American Math. Society
  38.     ISBN 0-8218-5078-4 (2nd ed.)  1987
  39.  
  40. This has an extensive bibliography.
  41.  
  42. Primality Testing
  43. -----------------
  44.  
  45. (1) Probable prime methods
  46.  
  47. The subject is well-covered in Bressoud's and Riesel's books.
  48. You should also read:
  49.  
  50. (a) Brillhart, Lehmer, & Selfridge
  51.     New Primality Criteria and factorizations of 2^n +/- 1.  
  52.     Math. Comp. Vol 29 1975, pp 620-647
  53.  
  54. (b) Pomerance, Selfridge, & Wagstaff Jr.
  55.     The pseudoprimes to 25*10^9
  56.     Math. Comp. Vol 35 1980 pp. 1003-1026
  57.  
  58. (2) Lucas-Lehmer methods and extensions
  59.  
  60. (a) H.C. Williams & J.S. Judd
  61.     Determination of the primality of N by using factors of N^2 +/- 1
  62.     Math. Comp. Vol 30, 1976, pp 157-172
  63.  
  64.     Some algorithms for prime testing using generalized Lehmer functions
  65.     Math. Comp. Vol 30, 1976  pp. 867-886
  66.  
  67. (b) H.C. Williams & R. Holte
  68.     Some observations on primality testing
  69.     Math. Comp. Vol 32, 1978, pp. 905-917
  70.  
  71. (3) Cohen-Lenstra-Bosma cyclotomic ring methods
  72.  
  73. (a) Adelman, Pomerance, & Rumely
  74.     On distinguishing prime numbers from composite numbers
  75.     Ann. of Math. Vol 117, 1983,  pp. 173-206
  76.  
  77. (b) H. Cohen & A. Lenstra
  78.     Implementation of a new primality test
  79.     Math. Comp. Vol 48, 1987, pp. 103-121
  80.  
  81. (c) H. Cohen & H. Lenstra Jr.
  82.     Primality testing and Jacobi sums
  83.     Math. Comp. Vol 42, 1984, pp. 297-330
  84.  
  85. The most comprehensive work is: [N.B. 300 pages with lengthy bibliography]
  86.  
  87. (d) W. Bosma & M. van der Hulst
  88.     Primality Testing with Cyclotomy
  89.     Thesis, University of Amsterdam Press.
  90.  
  91.  
  92. (4) Atkin-Morain-Goldwasser elliptic curve methods
  93.  
  94.     The definitive work to date is:
  95.  
  96. (a)  F. Morain
  97.     Implementation of the Goldwasser-Killian-Atkin primality testing algorithm
  98.     Report, University of Limoges, Project Algo, 1988
  99.  
  100. This too has an extensive bibliography.
  101.  
  102.  
  103. Factoring
  104. ---------
  105.  
  106. (1) Pollard P+/-1 , Pollard Rho and Elliptic Curve Methods
  107.  
  108. The most comprehensive and best paper to date is:
  109.  
  110. (a) P. Montgomery
  111.     Speeding the Pollard and elliptic curve methods of factorization
  112.     Math. Comp. Vol. 48, 1987, pp. 243-265
  113.  
  114. See also
  115.  
  116. (b) P. Montgomery & R. Silverman
  117.     An FFT extension to the P-1 factoring algorithm
  118.     Math. Comp. Vol. 54, 1990, pp. 839-854
  119.  
  120. (c) P. Montgomery
  121.     An FFT extension of the elliptic curve method of factorization
  122.     Doctoral Dissertation, UCLA, 1992
  123.  
  124. (d) R. Silverman & S. Wagstaff Jr.
  125.     A practical analysis of the elliptic curve factoring algorithm
  126.     Math. Comp. (to appear July 1993)
  127.  
  128. (2) CFRAC
  129.  
  130. (a) J. Brillhart & M. Morrison
  131.    A Method of Factoring and the factorization of F7
  132.    Math. Comp.  Vol 29, 1975 pp. 183-205
  133.  
  134. (3) Quadratic Sieve
  135.  
  136. (a) R. Silverman
  137.     The Multiple Polynomial Quadratic Sieve
  138.     Math. Comp. Vol 48, 1987, pp. 329-339
  139.  
  140. (b) T. Caron & R. Silverman
  141.     Parallel implementation of the quadratic sieve
  142.     J. Supercomputing, Vol. 1, 1988 pp. 273-290
  143.  
  144. (4) Number Field Sieve
  145.  
  146. (a) A. Lenstra, H. Lenstra Jr., M. Manasse, & J. Pollard
  147.     The Number Field Sieve
  148.      Proc. 1990 ACM STOC Conf.
  149.  
  150. (b) J. Buhler, H. Lenstra, & C. Pomerance
  151.     Factoring integers with the number field sieve
  152.     Preprint 1992
  153.  
  154. (5) Class Group & related methods
  155.  
  156. (a) C.P. Schnorr & H. Lenstra Jr.
  157.     A Monte-Carlo factoring algorithm with linear storage
  158.     Math. COmp. Vol 43, 1984, pp. 289-311
  159.  
  160. (b) D. Shanks
  161.     Class Number, A theory of factorization and genera
  162.     Proc. Symp. Pure Math. Vol 20 , 1970 pp 415-440
  163.  
  164. (6) Cyclotomic field methods
  165.  
  166. (a) E. Bach & J. Shallit
  167.     Factoring with Cyclotomic Polynomials
  168.     Math. Comp. Vol. 52, 1989, pp. 201-218
  169.  
  170.  
  171. (7) General Approach
  172.  
  173. (a) J. Brillhart, P. Montgomery, & R. Silverman
  174.     Tables of factorizations of Fibonacci and Lucas Numbers
  175.     Math. Comp. Vol. 50, 1988, pp. 251-260
  176. --
  177. Bob Silverman
  178. These are my opinions and not MITRE's.
  179. Mitre Corporation, Bedford, MA 01730
  180. "You can lead a horse's ass to knowledge, but you can't make him think"
  181.