Primality Proving Package

This package implements primality proving. If ProvablePrimeQ[n] returns True, then the number can be mathematically proven to be prime. In addition, PrimeQCertificate[n] prints a certificate that can be used to verify that is prime or composite.

ProvablePrimeQ[n]gives True if n can be proved to be prime, and False if n can be proved to be composite
ProvablePrimeQ[n, "Certificate"->True]prints a certificate that can be used to verify the result
PrimeQCertificate[n]prints a certificate that n is prime or that n is composite
PrimeQCertificateCheck[cert,n]verifies that the certificate cert proves the primality or compositeness of n

Proving primality or compositeness.

The functions provided in this package not only prove primality, but 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]:=
Click for copyable input
PrimeQ indicates that the number 1093 is prime.
In[2]:=
Click for copyable input
Out[2]=
ProvablePrimeQ gives the same result, but it has generated a certificate.
In[3]:=
Click for copyable input
Out[3]=
This prints the certificate.
In[4]:=
Click for copyable input
Out[4]=
This prints the certificate directly.
In[5]:=
Click for copyable input
Out[5]=

The certificate of primality used in this package for large n is based on the theory of elliptic curves.

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 , which is intended to show that is not equal to .

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]:=
Click for copyable input
Out[6]=
This verifies primality using the certificate.
In[7]:=
Click for copyable input
Out[7]=
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]:=
Click for copyable input
Out[8]=
This verifies the compositeness.
In[9]:=
Click for copyable input
Out[9]=

This package is not meant to replace the builtin primality tester PrimeQ but rather to allow you to be completely secure that a number is truly prime. The package should be used only to certify results after all the number theoretic 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 you 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.

option name
default value
"SmallPrime"10^50lower bound for using the AtkinMorain primality test
"Certificate"Falsewhether to print a certificate
"PollardPTest"Automaticwhether to apply the Pollard factoring algorithm in the search for the next prime in the recursive certificate
"PollardRhoTest"Automaticwhether to apply the Pollard factoring algorithm in the search for the next prime in the recursive certificate
"TrialDivisionLimit"Automaticnumber of primes to be used in the trial division part of PrimeQCertificate
"PrimeQMessages"Falsewhether to print out the progress of the algorithm

Options for ProvablePrimeQ and PrimeQCertificate.

When is larger than the value of the option , ProvablePrimeQ uses the AtkinMorain test as described above.

Note that you must use the same value of when you check a certificate using PrimeQCertificate that you used when you generated it using ProvablePrimeQ or PrimeQCertificate.

Since the default value of is larger than the given number, Pratt's certificate of primality is returned.
In[10]:=
Click for copyable input
Out[10]=
For large numbers, the certificate can be quite long and involved.
In[11]:=
Click for copyable input
Out[11]=