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 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