Pratt's Primality Certificates (Q7361797)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Pratt_Certificate
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Pratt's Primality Certificates |
AFP entry Pratt_Certificate |
Statements
22 July 2013
0 references
Simon Wimmer
0 references
Lars Noschinski
0 references
Pratt's Primality Certificates (English)
0 references
In 1975, Pratt introduced a proof system for certifying primes. He showed that a number p is prime iff a primality certificate for p exists. By showing a logarithmic upper bound on the length of the certificates in size of the prime number, he concluded that the decision problem for prime numbers is in NP. This work formalizes soundness and completeness of Pratt's proof system as well as an upper bound for the size of the certificate.
0 references
