Industrial-grade prime: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 00:47, 14 January 2022

Industrial-grade primes (the term is apparently due to Henri Cohen^[1]) are integers for which primality has not been certified (i.e. rigorously proven), but they have undergone probable prime tests such as the Miller–Rabin primality test, which has a positive, but negligible, failure rate, or the Baillie–PSW primality test, which no composites are known to pass.

Industrial-grade primes are sometimes used instead of certified primes in algorithms such as RSA encryption, which require the user to generate large prime numbers. Certifying the primality of large numbers (over 100 digits for instance) is significantly harder than showing they are industrial-grade primes. The latter can be done almost instantly with a failure rate so low that it is highly unlikely to ever fail in practice. In other words, the number is believed to be prime with very high, but not absolute, confidence.

References

^ Chris Caldwell, The Prime Glossary: probable prime at The Prime Pages.

This number theory-related article is a stub. You can help Wikipedia by expanding it.

[1] Chris Caldwell, The Prime Glossary: probable prime at The Prime Pages.

[1]

@@ Line 1: / Line 1: @@
-'''Industrial-Grade primes''' are integers for which primaily has not been certified (i.e. rigorously proven), but have undergone a test such as the Miller-Rabin primality test, which has a positive, but impossibly low, failure rate.
+'''Industrial-grade primes''' (the term is apparently due to [[Henri Cohen (number theorist)|Henri Cohen]]<ref>Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=PRP ''The Prime Glossary: probable prime''] at The [[Prime Pages]].</ref>) are [[integer]]s for which [[primality]] has not been certified (i.e. rigorously proven), but they have undergone [[probable prime]] tests such as the [[Miller–Rabin primality test]], which has a positive, but negligible, failure rate, or the [[Baillie–PSW primality test]], which no composites are known to pass.
-Industrial-grade primes are often used instead of certified pirmes in algorithms such as [[RSA encryption]], which require the user to generate large prime numbers.  Say, for example, that I need to test a number that is 100 digits long for primality.  Certifying primality for this number would be extremely difficult, even using modern methods.  (Trying to prove primality by simply testing every possible prime factor less than it at a trillion trial divisions per second would take over 100000000000000000000 (10^20) times the [[age of the universe]]).  However, an industrial-grade prime test can accurately test this number for primality almost instantly within an impossibly low failure rate.
+Industrial-grade primes are sometimes used instead of certified primes in [[algorithms]] such as [[RSA encryption]], which require the user to generate large [[prime numbers]].  [[Primality test|Certifying the primality]] of large numbers (over 100 digits for instance) is significantly harder than showing they are industrial-grade primes. The latter can be done almost instantly with a [[failure rate]] so low that it is highly unlikely to ever fail in practice. In other words, the number is believed to be prime with very high, but not absolute, confidence.
+== References ==
+{{Reflist}}
+{{Prime number classes}}
 [[Category:Cryptographic algorithms]]
 [[Category:Prime numbers]]
-{{num-stub}}
+{{numtheory-stub}}