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>
- speed of "PrimeQ"