rich@jvncf.csc.org..csc.org (Seth I. Rich) (07/24/87)
I posted a plea for help some time ago, and I've received my share of it.
At the request of several people, I'm gonna post a summary of what people
have sent me. Please correct me if any of it is wrong or if anything is
glaringly missing. The E-Mail address, regardless of what it says above,
is rich@jvncf.csc.org. Thanks.
The people responding: Ed Hook, Tom Dube, Matt Crawford, Joe Buck, Mark Lerner,
Lou Fernandez, Anthony without a last name,
Bob Silverman, Burch Seymour, John Hanley, James Dugal.
One thing resulting from my request is an argument (now ended) about the
whereabouts of H. Lenstra. I didn't mean to start any disputes, guys...
Also, to the one person who sent me an algorithm from Knuth without indicating
source, shame on you! You should know better!
And to the chap who said to divide by everything up to its square root and look
for a zero remainder, thanks a lot. You brightened my day. :-)
OK...to the results:
The Lucas-Lehmer test for deciding the primality of a Mersenne number.
Knuth vol. 2 section 4.5.? was recommended highly by numerous people (with
good reason).
In recent years, there are supposedly several good articles in SCIENTIFIC
AMERICAN, at least one by Carl Pomerance
"A Fast Monte-Carlo Test for Primality", Solovay and Strassen, SIAM Journal
of Computing, vol. 6, no. 4, December/March 1977, pp 84-85 (I
received varying dates for this article, so I post them all)
Kranakis' thesis (Yale) was published in book form.
Riesel's PRIME NUMBERS AND COMPUTER METHODS OF FACTORIZATION, Birkhauser,
1985(?)
Rivest, Shamir, and Adleman, "A Method for Obtaining Digital Signitures and
Public-key Cryptosystems", April 1977, MIT/LCS/TM-82
J.F. Traub, ed., ALGORITHMS AND COMPUTING, Academic Press, 1976
Mathematics of Computation, vol. 29, "New Primality Criteria and Factorizations
of 2^N +/- 1", by Brillhart, Lehmer, and Selfridge
Mathematics of Computation, volumes 30,31, and 33 have articles by Hugh
Williams.
MAA Lecture Notes #4
As-Yet-Unpublished "Algorithms in Number Theory", by A. Lenstra and H. Lenstra
JOURNAL OF NUMBER THEORY, vol. 12 (1980), M.O. Rabin, "Probabilistic
Algorithms for Testing Primality", pp 128-138
And, for a good book or two on number theory...
M. R. Schroeder, NUMBER THEORY IN SCIENCE AND COMMUNICATION (for EE and CS
types)
Niven and Zuckerman, AN INTRODUCTION TO THE THEORY OF NUMBERS, Wiley, 1972
K. H. Rosen, ELEMENTARY NUMBER THEORY AND ITS APPLICATIONS, 1984 (discusses
Rabin's paper above)
Much thanks, please respond if something's wrong/missing, and thank you for
your support.
- Seth I. Rich