# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Obtain a certificate showing that a number is prime or composite

Contributed by:
Wolfram Research

ResourceFunction["PrimeQCertificate"][ gives a certificate that |

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.

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

In[1]:= |

Out[1]= |

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

In[2]:= |

Out[2]= |

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

In[3]:= |

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, 2^{p-1}≡1mod *p* if *p* is prime:

In[4]:= |

Out[4]= |

Wolfram Language 11.3 (March 2018) or above

- 1.0.0 – 07 March 2019

This work is licensed under a Creative Commons Attribution 4.0 International License