Pratt Certificates of Primality
Wolfram Demonstrations Project · 2007
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 n