Mathematica 9 is now available

SEARCH MATHEMATICA 8 DOCUMENTATION

THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.

Primality Proving Package >

Primality Proving Package Symbol

Tutorials »|See Also »|More About »

PrimeQCertificate

PrimeQCertificate[n]
gives a certificate that n is prime or that n is composite.

MORE INFORMATION

To use PrimeQCertificate, you first need to load the Primality Proving Package using Needs["PrimalityProving`"].

PrimeQCertificate uses the Pratt certificate and the Atkin-Morain certificate for primality.

A certificate of compositeness is a list of 3 integers, either {a, n-1, n} or {a, 2, n}, with .

A prime p always satisfies a^p-11 mod p. The certificate {a, n-1, n} can be used to show that n is composite by demonstrating that a^n-11 mod n.

Any number a whose square is 1mod n for n prime must satisfy a±1 mod n. The certificate {a, 2, n} can be used to show that n is composite by demonstrating that a±1mod n and a²1 mod n.

A certificate of primality consists of a recursive list of certificates which prove that n is a prime if one or more smaller numbers are prime as well.

PrimeQCertificate has the same options as ProvablePrimeQ.

Basic Examples (2)

Needs["PrimalityProving`"]

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

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

Needs["PrimalityProving`"]

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

The output is a list of 3 integers that indicate 1093 3511 is composite, and that it violates Fermat's little theorem for primes, 2^p-1

1 mod p if p is prime:

ProvablePrimeQ PrimeQCertificateCheck PrimeQ

Primality Proving Package

Primality Proving Package

© 2013 Wolfram Research, Inc.

Ask a question about this page | Suggest an improvement | Leave a message for the team