PrimalityProving`
PrimalityProving`
ProvablePrimeQ
Details and Options
- To use ProvablePrimeQ, you first need to load the Primality Proving Package using Needs["PrimalityProving`"].
- When ProvablePrimeQ[n] returns True, then n is prime based on the Pratt certificate of primality or the Atkin–Morain certificate of primality.
- ProvablePrimeQ should not be used as a replacement for PrimeQ, as PrimeQ is several orders of magnitude faster. Instead, use 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 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
open allclose allBasic Examples (1)Summary of the most common use cases
In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-db6dyf
PrimeQ indicates that 1093 is prime:
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-hqi
Out[2]=2

ProvablePrimeQ gives the same result, but it has generated a certificate:
In[3]:=3

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-xuk
Out[3]=3

Scope (2)Survey of the scope of standard use cases
In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-hv7lri
ProvablePrimeQ works on arbitrarily large numbers:
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-vtiy0j
Out[2]=2

In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-qekr3r
ProvablePrimeQ automatically threads over lists:
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-jzkvr
Out[2]=2

Options (2)Common values & functionality for each option
Certificate (1)
In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-begaws
Use the option "Certificate"->True to view the certificate directly:
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-bm3
Out[2]=2

PrimeQMessages (1)
In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-fgqpks
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-oet
Out[2]=2

Progress messages are printed with "PrimeQMessages"->True:
In[3]:=3

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-bv1
Out[3]=3

Properties & Relations (1)Properties of the function, and connections to other functions
In[1]:=1

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-d5tdbt
In[2]:=2

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-ehy
Out[2]=2

If ProvablePrimeQ has returned a result, use PrimeQCertificate to print the certificate:
In[3]:=3

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-n2k
Out[3]=3

In[4]:=4

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-w2d
Out[4]=4

With "Certificate"->True, ProvablePrimeQ repeats the Atkin–Morain primality test:
In[5]:=5

✖
https://wolfram.com/xid/005n3yzmn9pvj57al3ids8gxq2b-ek5
Out[5]=5
