Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PrimeQCertificate

Source Notebook

Obtain a certificate showing that a number is prime or composite

Contributed by: Wolfram Research

ResourceFunction["PrimeQCertificate"][n]

gives a certificate that n is prime or that n is composite.

Details and Options

ResourceFunction["PrimeQCertificate"] uses the Pratt certificate and the Atkin-Morain certificate for primality.
A certificate of compositeness is a list of three integers, either {a,n-1,n} or {a,2,n}, with |a|≠1.
A prime p always satisfies . The certificate {a,n-1,n} can be used to show that n is composite by demonstrating that .
Any number a whose square is 1mod n for n prime must satisfy . The certificate {a,2,n} can be used to show that n is composite by demonstrating that and .
A certificate of primality consists of a recursive list of certificates which prove that n is a prime if one or more smaller numbers is prime as well.
ResourceFunction["PrimeQCertificate"] has the same options as ProvablePrimeQ.

Examples

Basic Examples (2) 

A certificate that can be used to prove that 1093 is a prime:

In[1]:=
ResourceFunction["PrimeQCertificate"][1093]
Out[1]=

The same certificate can be obtained by using ProvablePrimeQ with the option "Certificate"→True:

In[2]:=
ResourceFunction["ProvablePrimeQ"][1093, "Certificate" -> True]
Out[2]=

A certificate that can be used to prove that 1093×3511 is composite:

In[3]:=
ResourceFunction["PrimeQCertificate"][1093 3511]
Out[3]=

The output is a list of three integers that indicate 1093×3511 is composite, and that it violates Fermat's little theorem for primes, 2p-1≡1mod p if p is prime:

In[4]:=
PowerMod @@ %
Out[4]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 1.0.0 – 07 March 2019

Related Resources

License Information