WOLFRAM

PrimalityProving`
PrimalityProving`

ProvablePrimeQ

ProvablePrimeQ[n]

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

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 AtkinMorain 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"1050lower bound for using the AtkinMorain test
    "Certificate"Falsewhether to print a certificate
    "PollardPTest"Automaticwhether to use the Pollard 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

open allclose all

Basic Examples  (1)Summary of the most common use cases

PrimeQ indicates that 1093 is prime:

Out[2]=2

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

Out[3]=3

Scope  (2)Survey of the scope of standard use cases

ProvablePrimeQ works on arbitrarily large numbers:

Out[2]=2

ProvablePrimeQ automatically threads over lists:

Out[2]=2

Options  (2)Common values & functionality for each option

Certificate  (1)

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

Out[2]=2

PrimeQMessages  (1)

A random prime:

Out[2]=2

Progress messages are printed with "PrimeQMessages"->True:

Out[3]=3

Properties & Relations  (1)Properties of the function, and connections to other functions

Here is a random prime:

Out[2]=2

If ProvablePrimeQ has returned a result, use PrimeQCertificate to print the certificate:

Out[3]=3
Out[4]=4

With "Certificate"->True, ProvablePrimeQ repeats the AtkinMorain primality test:

Out[5]=5

Possible Issues  (1)Common pitfalls and unexpected behavior

A certificate cannot be generated for , , or :

Out[2]=2