[Date Index] [Thread Index] [Author Index]

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>