Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ProvablePrimeQ

Source Notebook

Certify a number as provably prime

Contributed by: Wolfram Research

ResourceFunction["ProvablePrimeQ"][n]

gives True if n is provably prime, and False otherwise.

Details and Options

When ResourceFunction["ProvablePrimeQ"][n] returns True, then n is prime based on the Pratt certificate of primality or the Atkin-Morain certificate of primality.
ResourceFunction["ProvablePrimeQ"] should not be used as a replacement for PrimeQ, as PrimeQ is several orders of magnitude faster. Instead, use ResourceFunction["ProvablePrimeQ"] to certify the results of PrimeQ when needed.
The following options can be given:
"SmallPrime"1050lower bound for using the Atkin-Morain test
"Certificate"Falsewhether to print a certificate
"PollardPTest"Automaticwhether to use the Pollard p-1 method
"PollardRhoTest"Automaticwhether to use the Pollard ρ method
"TrialDivisionLimit"Automaticnumber of primes to use in trial division
"PrimeQMessages"Falsewhether progress is to be monitored

Examples

Basic Examples (2) 

PrimeQ indicates that 1093 is prime:

In[1]:=
PrimeQ[1093]
Out[1]=

ProvablePrimeQ gives the same result, but it has generated a certificate:

In[2]:=
ResourceFunction["ProvablePrimeQ"][1093]
Out[2]=

Scope (2) 

ProvablePrimeQ works on arbitrarily large numbers:

In[3]:=
ResourceFunction["ProvablePrimeQ"][10^300 + 3]
Out[3]=

ProvablePrimeQ automatically threads over lists:

In[4]:=
ResourceFunction["ProvablePrimeQ"][{3, 7, 9, 13}]
Out[4]=

Options (3) 

Certificate (1) 

Use the option "Certificate"→True to view the certificate directly:

In[5]:=
ResourceFunction["ProvablePrimeQ"][1093, "Certificate" -> False]
Out[5]=
In[6]:=
ResourceFunction["ProvablePrimeQ"][1093, "Certificate" -> True]
Out[6]=

PrimeQMessages (2) 

A random prime:

In[7]:=
p = RandomPrime[{10^60, 10^61}]
Out[7]=

Progress messages are printed with "PrimeQMessages"→True:

In[8]:=
ResourceFunction["ProvablePrimeQ"][p, "PrimeQMessages" -> True]
Out[8]=

Properties and Relations (3) 

Here is a random prime:

In[9]:=
p = RandomPrime[{10^9, 10^12}]
Out[9]=

If ProvablePrimeQ has returned a result, use ResourceFunction["PrimeQCertificate"] to print the certificate:

In[10]:=
ResourceFunction["ProvablePrimeQ"][p]
Out[10]=
In[11]:=
ResourceFunction["PrimeQCertificate"][p]
Out[11]=

With "Certificate"→True, ProvablePrimeQ repeats the Atkin-Morain primality test:

In[12]:=
ResourceFunction["ProvablePrimeQ"][p, "Certificate" -> True]
Out[12]=

Possible Issues (1) 

A certificate cannot be generated for -1, 0, or 1:

In[13]:=
ResourceFunction["ProvablePrimeQ"][0]
Out[13]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 1.0.0 – 07 March 2019

License Information