Re: PrimeQ queries
- To: mathgroup at smc.vnet.net
- Subject: [mg24239] Re: PrimeQ queries
- From: "Atul Sharma" <atulksharma at yahoo.com>
- Date: Mon, 3 Jul 2000 20:39:20 -0400 (EDT)
- References: <8jk658$34j@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
The PrimeQ function combines two strong pseudoprime tests (base 2 and base
3) and the Lucas pseudoprime test, with the results correct up to 10^16 (no
known counterexamples and all known primes correctly identified). Beyond
this number, the PrimeQ results may be false. For an entertaining and
comprehensive discussion of Mathematica's PrimeQ and alternate tests of
primality, you might want to see Chapter 18 (Certifying Primality) in Stan
Wagon's Mathematica in Action (Telos, 1998). Chapter 2 (Prime Numbers) is
more basic, but includes a review of strong pseudoprime tests, which are
based on Fermat's Little theorem: if p is prime then a^(p-1) congruent to 1
(mod p) if gcd(a,p) =1. The converse is not true, with those integers that
fail called strong pseudoprimes. For the 2-strong pseudoprime test, for
example, we might infer that if n is odd and 2^(n-1) is congruent to 1 (mod
1), then n is prime. There are however, 22 counterexamples below 10000,
shown here as integers which pass the 2-strong test but not PrimeQ.
In[19]:=
pseudoprime[n_] :=\[InvisibleSpace]! PrimeQ[n] && PowerMod[2, n - 1, n] == 1
Select[Range[10000], pseudoprime]
{341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033,
\
4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911}
By combining it with the 3-strong pseudoprime test, the first false result
occurs at 1,373,653. In the same manner, combining strong pseudoprime tests
for 2,3,5,7,11 will work up to 25 x 10^9.
HTH
Atul
Greg Keogh wrote in message <8jk658$34j at smc.vnet.net>...
>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>
>
>
>