Why should I switch to Python? - Infinity of Primes

[Harald Hanche-Olsen]

+ dave white <dwhite2 at seas.upenn.edu>:

| Since we're on the subject of primes...  I've heard that there's a
| nice probabilistic algorithm for computing large primes using
| Fermat's Little Theorem.  Python seems like it would be well suited
| for this since bignums are built into the language.  Does anyone
| know this algorithm?

You're thinking of using FLT for primality *testing*, not for
*computing* primes.  The algorithm is trivial to explain:

Assume p is an integer, suspected to be a prime.  Pick an integer a
such that 2 <= a < p and compute a**(p-1) mod p.  If you get 1, then p
*may* be a prime, but again it may not.  Repeat to gain more
confidence.  On the other hand, if you don't get 1, p is definitely
not a prime.

To find large probable primes using this algorithm, pick large odd
numbers at random and subject them to the test until you find one that
passes the test for sufficiently many different a to give you that
warm fuzzy feeling that surely, this must be a prime.

Unfortunately, there are some composite numbers that will always pass
this test.  These are called pseudoprimes.

On the other hand, there are other probabilistic primality tests that
don't have this weakness.  Perhaps the best known is the Miller-Rabin
test, which just like the FLT test is applied with numbers a between 2
and p, and which always succeeds when p is a prime.  Moreover, the
Miller-Rabin test has the pleasant property that it fails for at least
3/4 of the available values a when p is composite, so that, e.g., 20
successful iterations of the test gives you roughly a billion to one
confidence in the primality of p.

I'd post some code, but all I have is some five year old Scheme code,
and that is probably not all that appropriate in this group.  The
comments to that old code has two literature references, though:

;;; Monier: Evaluation and comparison of two efficient
;;; probabilistic primality testing algorithms,
;;; Theoretical Computer Science 12 (1980) 97-108

;;; A.O.L. Atkin and R.G. Larson: On a primality test of Soloway 
;;; and Strassen, SIAM J. Comput. 11 (1984), 789-791

If you go surfing the web you'll probably find lots of implementations
in every language known to man, however.

And-for-dessert-there-is-primality-*proving*-using-elliptical-curves-ly y'rs,

-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
   a wonderful obstruction to the mind."  - Francis Bacon