speed of "PrimeQ"

• To: mathgroup at smc.vnet.net
• Subject: [mg22860] speed of "PrimeQ"
• From: "Matthew Herman" <Henayni at hotmail.com>
• Date: Sat, 1 Apr 2000 21:00:17 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

```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? I mean, even FactorInteger is slower than some DOS
factorization programs.

Matt

```

• Prev by Date: RE: helpbrowser fonts in the menu boxes
• Next by Date: Volume
• Previous by thread: RE: Eigensystem Error on Machine Precision Matrices
• Next by thread: Re: speed of "PrimeQ"