Re: PrimeQ queries
- To: mathgroup at smc.vnet.net
- Subject: [mg24233] Re: [mg24213] PrimeQ queries
- From: "Matt Herman" <Henayni at hotmail.com>
- Date: Mon, 3 Jul 2000 20:39:16 -0400 (EDT)
- References: <200007010721.DAA03300@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hello! Mathematica 3.0 and 4.0 both catch that these numbers are composite.
I am surprised that Mathematica 2.2 was false on both numbers! I believe PrimeQ uses
some trial division. It should catch 89. Mathematica 3 and 4 both use the
Miller-Rabin probabilistic test.
Here is what the mathematica book says:
"PrimeQ first tests for divisibility using small primes, then uses the
Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a
Lucas test. "
"As of 1997, this procedure is known to be correct only for n<10^16, and it
is conceivable that for larger n it could claim a composite number to be
So, yes, there is an upper bound (10^16). Note however, that if a number is
output as composite, it is 100% composite.
"The package NumberTheory`PrimeQ` contains a much slower algorithm which has
been proved correct for all n. It can return an explicit certificate of
So, if you have Mathematica 3 or 4, you can use ProvablePrimeQ (it is much
slower, but you get a certificate).
----- Original Message -----
From: "Greg Keogh" <greg at mira.net>
To: mathgroup at smc.vnet.net
Subject: [mg24233] [mg24213] PrimeQ queries
> Hello from Melbourne Australia,
> I stumbled across some educational notebooks during the week that teach
> basic number theory. One of them contained this function that surprised
> primeQ[n_]:=PrimeQ[n] && n!=89*11551*37159 && n<10^15
> Further down I discover that the built-in PrimeQ incorrectly reports these
> numbers as prime:
> 89*11551*37159 = 38200901201
> 7309*321553*2828197 = 6646915915638769
> I didn't know that PrimeQ had "flaws" in it like this, or that it had an
> upper limit of reliability around 10^15. Could someone point me to some
> resources that might explain more on this matter?
> Some related questions:
> * What algorithm does Mathematica 2.2 use in PrimeQ? Has it been changed
> later releases?
> * Can someone point me to sample code to implement the Miller-Rabin
> primality test with selectable numbers of witnesses?
> Greg Keogh <greg at mira.net>
Prev by Date:
RE: implicit function
Next by Date:
Re: Re: Evaluate and HoldAll
Previous by thread:
Next by thread:
Re: PrimeQ queries