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> > > >