provable prime

{{Short description|Prime integer calculated using a primality-proving algorithm}}

{{distinguish|Probable prime}}

In number theory, a provable prime is an integer that has been calculated to be prime using a primality-proving algorithm. Boot-strapping techniques using Pocklington primality test are the most common ways to generate provable primes for cryptography.{{citation|title=An Introduction to Fast Generation of Large Prime Numbers|series=Philips Journal of Research|author=C. Couvreur and J. J. Quisquater|volume=37|year=1982|pages=231–264}}{{cite book |last1= Crandall |first1= Richard|last2=Pomerance |first2= Carl|date=2005 |title=Prime Numbers: A Computational Perspective |publisher= Springer|isbn=978-0387-25282-7|pages=174–178}}

Contrast with probable prime, which is likely (but not certain) to be prime, based on the output of a probabilistic primality test.

In principle, every prime number can be proved to be prime in polynomial time by using the AKS primality test. Other methods which guarantee that their result is prime, but which do not work for all primes, are useful for the random generation of provable primes.{{citation|title=RSA and Public-Key Cryptography|series=Discrete Mathematics and Its Applications|first=Richard A.|last=Mollin|publisher=CRC Press|year=2002|isbn=9781420035247|pages=124–125|url=https://books.google.com/books?id=mZUYNy0UGNUC&pg=PA124}}.

Provable primes have also been generated on embedded devices.{{Cite journal|last=Christophe|first=Clavier|title=Generating Provable Primes Efficiently on Embedded Devices|url=https://www.iacr.org/archive/pkc2012/72930372/72930372.pdf|journal=The International Association for Cryptologic Research}}