Function Repository Resource:

# ProvablePrimeQ

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" 1050 lower bound for using the Atkin-Morain test "Certificate" False whether to print a certificate "PollardPTest" Automatic whether to use the Pollard p-1 method "PollardRhoTest" Automatic whether to use the Pollard ρ method "TrialDivisionLimit" Automatic number of primes to use in trial division "PrimeQMessages" False whether progress is to be monitored

## Examples

### Basic Examples (2)

PrimeQ indicates that 1093 is prime:

 In[1]:=
 Out[1]=

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

 In[2]:=
 Out[2]=

### Scope (2)

ProvablePrimeQ works on arbitrarily large numbers:

 In[3]:=
 Out[3]=

 In[4]:=
 Out[4]=

### Options (3)

#### Certificate (1)

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

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=

#### PrimeQMessages (2)

A random prime:

 In[7]:=
 Out[7]=

Progress messages are printed with "PrimeQMessages"True:

 In[8]:=
 Out[8]=

### Properties and Relations (3)

Here is a random prime:

 In[9]:=
 Out[9]=

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

 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=

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

 In[12]:=
 Out[12]=

### Possible Issues (1)

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

 In[13]:=
 Out[13]=

## Requirements

Wolfram Language 11.3 (March 2018) or above

## Version History

• 1.0.0 – 07 March 2019