From: Paul Abbott
Newsgroups: sci.math.symbolic
Subject: Re: Primality Testing -- MMA, Macsyma, Axiom, Reduce, etc.
Date: Tue, 03 Dec 1996 12:54:40 +0800
paulp@gte.net wrote:
> I am currently working on a web page on compositeness tests
> and was wondering if anyone could tell me which algorithms
> (e.g., Rabin-Miller + a Lucas test) the common symbolic math packages
> each use to "test primality". I'm aware of what algorithms _can_ be
> used; what I'm interested in is what _was_ implemented in the
> current version each program.
Here is the (abbreviated) on-line documentation for the Mathematica
NumberTheory`PrimeQ` package:
This package implements primality proving. If ProvablePrimeQ[n] returns
True, then the number n can be mathematically proven to be prime. In
addition, PrimeQCertificate[n] prints a certificate that can be used to
verify that n is prime or composite. Note that the built-in primality
testing function PrimeQ does not actually give a proof that a number is
prime. However, as of this writing, there are no known examples where
PrimeQ fails.
Proving primality or compositeness.
The functions provided in this package not only prove primality, but
they also generate a certificate of primality. A certificate of
primality is a relatively short set of data that can be easily used to
prove primality. The word "easily" means that using the data to prove
primality is much easier and faster than generating the data in the
first place. As a simple example of a certificate, the factors of a
composite number provide a certificate of compositeness. Multiplying the
numbers together to show that they are the factors is much easier than
finding the factors. The advantage of providing certificates is that the
user does not have to trust the internal mechanism of the algorithm that
generated the certificate. It is fairly easy to write a program (in any
system) that checks that the certificate provides a proof of primality.
This loads the package.
In[1]:= <True]
Out[5]={True,{1093,5,{2,{3,2,{2}},{7,3,{2,{3,2,{2}}}},{13,2,{2,{3,2,{2}}}}}}}
The certificate of primality used in this package for large n is based
on the theory of elliptic curves. The basic idea was discovered by S.
Goldwasser and J.Kilian, "Almost All Primes Can Be Quickly Certified,"
in Proc. 18th STOC, 1986, pp. 316-329.
Their algorithm was only of theoretical significance, however. A.O.L.
Atkin found a way to make it practical by using ideas from complex
multiplication, which is a branch of number theory that combines the
fields of complex analysis, Galois theory and modular forms. This method
was implemented very successfully by F. Morain in "Implementation of the
Atkin-Goldwasser-Kilian Primality Testing Algorithm,"INRIA Research
Report, # 911, October 1988. In November 1989, Morain was able to give a
primality proof for a 1065-digit number, the first "titanic" prime
(>1000 digits) to be tested without special purpose algorithms. Since
that time Atkin and Morain have written an extensive treatise on the
algorithm: A.O.L. Atkin and F. Morain, "Elliptic Curves and Primality
Proving," Mathematics of Computation, 1993, 29-68. For an introduction
to primality testing and elliptic curves, see D. Bressoud, Factorization
and Primality Testing, Springer-Verlag, 1989.
This package can also be used to generate certificates of compositeness
for composite numbers. These certificates are based on showing that
simple properties that are true of prime numbers are not true for the
given number.
For example, PrimeQCertificate[3837523] returns the certificate {2,
3837522, 3837523}, which is intended to show that 2^3837522 mod 3837523
is not equal to 1.
ProvablePrimeQ[n] returns True or False depending on whether n is prime
or not. The certificate for primality or compositeness is generated by
PrimeQCertificate[n]. ProvablePrimeQ calls PrimeQCertificate and stores
the result, so it does not take any extra time to create a certificate
once ProvablePrimeQ has returned an answer. The certificate generated by
PrimeQCertificate can be checked by PrimeQCertificateCheck. This
function recognizes whether the certificate asserts primality or
compositeness and then uses the certificate to verify the assertion.
This prints the certificate of the prime number.
In[6]:= ProvablePrimeQ[1093, Certificate -> True]
Out[6]=
{True,{1093,5,{2,{3,2,{2}},{7,3,{2,{3,2,{2}}}},{13,2,{2,{3,2,{2}}}}}}}
This verifies primality using the certificate.
In[7]:= PrimeQCertificateCheck[Last[%], 1093]
Out[7]= True
Here is the certificate for a composite number. You can recognize a
certificate of compositeness because it will always be a list of three
integers.
In[8]:= PrimeQCertificate[1093 * 3511]
Out[8]= {2,3837522,3837523}
This verifies the compositeness.
In[9]:= PrimeQCertificateCheck[%, 3837523]
Out[9]= True
In versions of Mathematica later than Version 2.2, the built-in
function PrimeQ uses the Rabin strong pseudoprime test and the Lucas
test. This procedure has been proved correct for all n < 2.5 x 10^10. As
of April 1991, the procedure has not been proved correct for larger n,
nor has a counterexample been found. However, it is a mathematical
theorem that when PrimeQ[n] returns False, the number n is genuinely
composite. Thus PrimeQ[n] can only fail if n is composite but PrimeQ
declares it to be prime. It is important to note that PrimeQ is
deterministic; no computations based on random numbers are involved.
This package is not meant to replace the built-in primality tester
PrimeQ but rather to allow one to be completely secure that a number is
truly prime. The package should be used only to certify results after
all the number theoretical work has been done. For example, it would be
a mistake to use ProvablePrimeQ as a primality test for an integer
factoring algorithm. Rather, only when the complete factorization has
been achieved (using PrimeQ for primality testing) would one use
ProvablePrimeQ to certify the primality of the prime factors given by
the algorithm. The reason for this is that PrimeQ will be, in general,
several orders of magnitude faster than ProvablePrimeQ. As noted above,
there is a possibility that PrimeQ is incorrect, that is, it asserts
that a number is prime when it is really composite. It is unclear
whether ProvablePrimeQ always detects this; but if it does, a warning
message is generated indicating a counterexample to PrimeQ, and False is
returned. This behavior can be simulated by artificially setting
PrimeQ[n] to True for a known composite n.
Here PrimeQ is artificially set to give an incorrect answer.
ProvablePrimeQ detects that PrimeQ is incorrect, prints a warning
message, and returns the correct answer.
In[10]:= (Unprotect[PrimeQ]; PrimeQ[38200901201] = True;
ProvablePrimeQ[38200901201])
SqrtMod::fail: Warning: $IterationLimit exceeded; PrimeQ[38200901201]
may be incorrect.
PrimeQCertificate::false: Warning: PrimeQCertificate has detected a
counterexample to PrimeQ; PowerMod[3, 38200901200, 38200901201] != 1.
Out[10]= False
Options for ProvablePrimeQ and PrimeQCertificate.
When n is larger than the value of the option SmallPrime, ProvablePrimeQ
uses the Atkin-Morain test as described above. This primality proving
algorithm is suboptimal if the number is within the range of efficient
factoring algorithms. When this is the case, a method of V. Pratt is
preferable: V. Pratt, "Every Prime Has a Succinct Certificate," SIAM
Journal of Computation 4 (1975), pages 214-220. An implementation of
this algorithm in Mathematica is described in S. Wagon, Mathematica in
Action, W. H. Freeman, 1991, Section 8.7.
Note that you must use the same value of SmallPrime when you check a
certificate using PrimeQCertificate that you used when you generated it
using ProvablePrimeQ or PrimeQCertificate.
Since the default value of SmallPrime is larger than the given number,
Pratt's certificate of primality is returned.
In[11]:= PrimeQCertificate[3511]
Out[11]= {3511,7,{2,{3,2,{2}},{5,2,{2}},{13,2,{2,{3,2,{2}}}}}}
Here, the value of SmallPrime has been reset so that it is less than the
given number. This causes the Atkin-Goldwasser-Kilian-Morain certificate
to be returned.
In[12]:= PrimeQCertificate[3511, SmallPrime -> 1000]
Out[12]= {{CertificatePrime->3511,
CertificatePoint->PointEC[2,2467,1447,2135,3511],
CertificateK->32,CertificateM->3424,
CertificateNextPrime->107,CertificateDiscriminant->7},107,
2,{2,{53,2,{2,{13,2,{2,{3,2,{2}}}}}}}}
For large numbers, the certificate can be quite long and involved.
In[13]:= PrimeQCertificate[10^20 + 39]
Out[13]= {{CertificatePrime->100000000000000000039,
CertificatePoint
->PointEC[2,1729260293697269439,64272530717713441964,
28545061435426883889,100000000000000000039],CertificateK->1012,
CertificateM->100000000010180551292,
CertificateNextPrime->98814229259071691,
CertificateDiscriminant->-43},{
CertificatePrime->98814229259071691,
CertificatePoint->PointEC[2,14775259946196422,20390237783617966,79469644695126438,
98814229259071691],CertificateK->2822600,
CertificateM->98814229876628200,
CertificateNextPrime->35008229957,CertificateDiscriminant->-7},{
CertificatePrime->35008229957,
CertificatePoint
->PointEC[5,11747318414,5556861890,30747969158,35008229957],
CertificateK->4,CertificateM->35008421452,
CertificateNextPrime->8752105363,CertificateDiscriminant->-7},
8752105363,
2,{2,{3,2,{2}},{7,3,{2,{3,2,{2}}}},{11,2,{2,{5,2,{2}}}},{13,
2,{2,{3,2,{2}}}},{43,3,{2,{3,2,{2}},{7,3,{2,{3,2,{2}}}}}},{33889,
13,{2,{3,2,{2}},{353,3,{2,{11,2,{2,{5,2,{2}}}}}}}}}}
_________________________________________________________________
Paul Abbott
Department of Physics Phone: +61-9-380-2734
The University of Western Australia Fax: +61-9-380-1014
Nedlands WA 6907 paul@physics.uwa.edu.au
AUSTRALIA http://www.pd.uwa.edu.au/Paul
God IS a weakly left-handed dice player
_________________________________________________________________