Re: speed of "PrimeQ"

*To*: mathgroup at smc.vnet.net*Subject*: [mg22873] Re: [mg22860] speed of "PrimeQ"*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sun, 2 Apr 2000 15:33:41 -0400 (EDT)*References*: <200004020200.VAA05226@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Matthew Herman wrote: > > Hi > > I was doing some work with PrimeQ, and I found that these > mathematica(3.0) "programs" are just as fast (or faster) as primeQ: > > prm4[n_Integer]:= If[PowerMod[3,n,n]==3,"n is prime or > carmichael", "n is composite"] > > prm3[n_Integer]:= > If[PowerMod[3,n,n]==3, > If[PowerMod[5,n,n]==5,"n is prime or carmichael","n is > pseudoprime"], > "n is composite"] > > Pep[n_Integer]:=If[PowerMod[3, (2^(2^n)-1), > (2^2^n)+1]-((2^2^n)+1)==-1, "Fn is prime", "Fn is composite". > > (this is pepin's test for fermat number primality). > > Timing[pep[15]] > > {2048.77 Second, Fn is composite}. > > Anyone know why this would be faster than a mathematica optimized > function? This is a bit silly. The implementation notes state clearly what tests PrimeQ performs, and obviously it attempts to rule out pseudoprimes. So it is simply doing a more complete job. I quote from the documentation, accessible from the help browser. "PrimeQ first tests for divisibility using small primes, then uses the MillerRabin strong pseudoprime test base 2 and base 3, and then uses the Lucas test. As of 1995, this procedure is known to be correct only for n < 2.5*10^10, and it is conceivable that for larger n it could claim a composite number to be prime. [Version 4 documentation: n < 10^16. --dl] The package NumberTheory`PrimeQ` contains a much slower algorithm which has been proved correct for all n. It can return an explicit certificate of primality." PrimeQ is known to do a bit more work than is necessary, and possibly there might be a better set of tests that could be done in the same time, but clearly it does a more careful job (e.g. using the Lucas test) than that to which you compare it. > I mean, even FactorInteger is slower than some DOS > factorization programs. This is a bit vague so I am not sure what to say. Are you comparing on some set of random examples? Integers in some size range? Integers of some special type e.g. Fermat numbers? Is FactorInteger slower across-the-board on your class of examples? Or only on some percentage? What DOS programs are in the comparison? It may again help to look at the implementation notes, from which I quote below. "FactorInteger switches between removing small primes by trial division and using the Pollard p-1, Pollard rho and continued fraction algorithm." I have found the speed of FactorInteger to be generally quite reasonable up to around 40 digits, which is not to say that other programs are never faster in that range. Also I think the speed remains tolerable up to maybe 55 digits though I confess I have not tested this too carefully. Beyond that size one really requires different algorithms such as a sieve or elliptic curve method; we may implement one or both in a future version (we have an add-on package that does ECM but it is not tuned very well for speed so far as I can tell). In any case, without more specific information and examples it is difficult to comment as to whether or why FactorInteger may be slow compared to expectations. Daniel Lichtblau Wolfram Research

**References**:**speed of "PrimeQ"***From:*"Matthew Herman" <Henayni@hotmail.com>