navbar-top.gif
btn_spacer.gifHomeTopicsLatestRandomAboutFAQsParticipateAuthoring Areabtn_spacer.gif

Pratt Certificates of Primality

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.
Powered by Wolfram Mathematica
Contact The Wolfram Demonstrations Project Team    Site Index    Wolfram Research
©  2008 The Wolfram Demonstrations Project & Contributors    Terms of Use    Privacy Policy    RSS    Atom