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

Greg, 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 prime." 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 primality. " So, if you have Mathematica 3 or 4, you can use ProvablePrimeQ (it is much slower, but you get a certificate). Matt ----- 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 me: > > 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 in > later releases? > > * Can someone point me to sample code to implement the Miller-Rabin > primality test with selectable numbers of witnesses? > > Cheers, > Greg Keogh <greg at mira.net> > > > >

**References**:**PrimeQ queries***From:*"Greg Keogh" <greg@mira.net>