From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Proving Primality
Date: 22 Oct 1996 15:44:26 GMT

In article <32646C6E.5B73@pop.source.co.uk>,
Garreth Jeremiah  <srcfjlmw@pop.source.co.uk> wrote:

>I need an algorithm that when presented with a number (not huge but large 
>enough say 100,000) will tell me if it is PRIME ornot.

Gee, I don't know, 100 000 digits is sort of huge and I... Oh, you said
the _number_ is only 100 000 or so! That's considered small.

You want a fast test? Compute 2^(N-1) mod N; if  N  is prime, this will
be  1; if  N  is composite, it's _usually_ not 1. Since exponentiation
can be done in log(N) steps, this is quite fast. Yes, it's not completely
reliable, but it's pretty good. Quoting from Pinch's survey article
on the subject (Notices AMS 40(1993) 1203-9), there are 264239 failures
of this test for  N  up to 10^13. If you have an upper bound on the size
of  N, it may be most efficient to simply use the Fermat test and
a look-up of false positives.

Not much slower is the computation of powers of small matrices mod N, 
which can be used to compute high-order terms of linear recurrence
relations mod  N. Thus you can use theorems like these:

Theorem.
Let  u_1=0, u_2=2, u_3=3 and then u_(n+1)=u_(n-1)+u_(n-2) for further n.
If  N  is prime, then  u_N = 0 mod  N. Conversely, if  u_N=0 mod  N,
then  N  is prime if  N < 16 000 000 unless  N=521^2 or n=7*13*9941

(By the way, this test also detects as composite all the exceptional
numbers listed in the Pinch article, except the 13-digit Fermat base-2
pseudoprime 6763 * 10627 * 29947, whose composite character can be
detected by another companion sequence related to the one listed above.)

dave