From: bobs@rsa.com Newsgroups: sci.math Subject: Prime Testing Date: Sun, 03 May 1998 11:40:09 -0600 In article <354B543E.7A116AFA@yorku.ca>#1/1, Allan Trojan wrote: > > I recently was amazed to learn that both Mathematica and Maple > use a probabilistic algorithm for determining primality. Although > this algorithm, using Lucas test, etc. is almost everywhere = 1, > it is not 100% certain, or at least not known to be. > > My question therefore is, what is the fastest known algorithm > that determines primality with ABSOLUTE 100% certainty??? Your question can not be answered without more information. (1) Do you require that the asymptotic complexity of the algorithm have a rigorous proof? (2) Fastest for what size primes? The Cyclotomy test is the fastest algorithm whose run time has been rigorously proved. It is also the fastest PRACTICAL test for numbers ranging from about 100 to several thousand decimal digits. Its run time is: O( log n ^(logloglog n)) The Elliptic Curve method is asymptotically faster than this, but its run time derivation depends on some unproved conjectures (which ARE believed to be true) in analytic number theory. These conjecture deal with the density of 'near primes' in short intervals, i.e. the density of integers kp where p is prime and k is tiny. The elliptic curve method is polynomial time. Its run time is O(log^6 n) and hence must ultimately be faster than the Cyclotomy method. The crossover point of the two methods will be implementation and computer architecture dependent. The crossover point is currently slightly above what can be practically computed. i.e. 'around' 10000 digits. [given existing implementations]. Faster still asymptotically is the deterministic version of Miller-Rabin. It depends however on the assumption that the Genealized Riemann Hypothesis is correct. The run time of this algorithm is O(log^4 n) using naiive methods for multiplication mod n and O(log^3 n loglog n logloglog n) using FFT methods. Where this method becomes faster than the other two already mentioned is not known. The crossover is out of current computing range. All of these methods are deterministic. Whether they prove primality with 100% certaintly is a matter of philosophical debate. The first two methods are sufficiently complicated that the probability of an error in their implementation exceeds the probability of error when a proababilistic algorithm says 'prime'. -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================== From: jpr2718@aol.com (Jpr2718) Newsgroups: sci.math Subject: Re: Minimum tests for a prime........... Date: 10 Aug 1998 00:56:38 GMT dominic wrote: > but is this the ABSOLUTE minimum amount of testing we must >carry out on the number to be exactly 100% sure that it is definately >in fact a prime ?? > There is a way to prove to someone else that a given number is a prime that frequently involves much less computation than checking divisors up to the square root. To set it up, you have to factor p-1, so it can't always be applied. It's call the "prime signature" method, and is described in an article by Dixon in the American Mathematical Monthly in 1986 (give or take a year or two). As I recall, you give the other person the factorization of p-1, and a primitive root, g, of p. All that needs to be done to prove that p is prime is to check that g^((p-1)/q) is not congruent to 1 mod p for any prime q that divides p-1. Find this written up somewhere before using the above; I might not have the story quite right. This is not necessarily the best way to determine whether a number is a prime in the first place, it's just a quick way to prove it to someone else in some cases.