Newsgroups: sci.math.num-analysis From: dik@cwi.nl (Dik T. Winter) Subject: Re: Finding If a number is a prime number Date: Sun, 10 Sep 1995 01:02:46 GMT In article m.cafaro@agora.stm.it (Massimo Cafaro) writes: > In article <810368182snz@rifai.demon.co.uk>, Yousef@rifai.demon.co.uk wrote: > > Does any one know of an algorithm which find out if a given number is a prime > > number? > > The one I know of involves calculating all the prime numbers less than > or equal > > the square root of the given number. > > Any algorithm which makes the computer do less work? ... > > The worst case running time of trial division is theta(sqrt(n)) if each > trial division takes constant time. Thus the running time is exponential > in the lenght of n. In fact if n is encoded in binary using k bits then > k=ceiling(lg(n+1)) and sqrt(n)=theta(2^(k/2)). > > There exist a better algorithm: the Miller-Rabin randomized primality > test. The procedure works as follow. Again a probabilistic algorithm. Good primality proving algorithms can be found through articles written by Arjen Lenstra and Henry Cohen. I think Henry Cohens package on long-integer arithmetic (pari) implements such an algorithm. Normally it costs only a few seconds to prove that a 50 digit number is prime. I just tried; on a SGI with MIPS R4K proving a particular 78 digit number prime took 11 seconds (and that was with a very old version of the program by Lenstra and Cohen). Of course, one of the things the program does is Miller-Rabin to weed out the obvious non- candidates; but it continues with other algorithms. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl