Provable prime

Not to be confused with Probable prime.

In number theory, a provable prime is an integer that has been calculated to be prime using a primality-proving algorithm. 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. In practice, 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.[1]

See also

References

  1. ↑ Mollin, Richard A. (2002), RSA and Public-Key Cryptography, Discrete Mathematics and Its Applications, CRC Press, pp. 124–125, ISBN 9781420035247.
This article is issued from Wikipedia - version of the 11/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.