Pratt Certificates of Primality

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A prime number can be proved prime by exhibiting all the prime factors of together with a witness such that but for each prime divisor of . The primes are then proved prime in the same way, except that 2 is assumed to be prime without proof. This recursive construction has a tree structure, which is shown here. These ideas prove that the prime numbers lie in the complexity class NP. If the input number is not prime, the next prime is used.

Contributed by: Stan Wagon (Macalester College) (March 2011)
Open content licensed under CC BY-NC-SA




Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.