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
- Follow-Ups:
- Re: speed of "PrimeQ"
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: speed of "PrimeQ"