Industrial-grade primes (the term is apparently due to
Henri Cohen Henri Cohen may refer to:
*Henri Cohen (composer) (1808–1880), French music theorist and composer
*Henri Cohen (water polo) (died 1930), Belgian water polo athlete
*Henri Cohen (number theorist)
Henri Cohen (born 8 June 1947) is a number theor ...
[Chris Caldwell]
''The Prime Glossary: probable prime''
at The Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.
The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
.) are
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s for which
primality
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
has not been certified (i.e. rigorously proven), but they have undergone
probable prime
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...
tests such as the
Miller–Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
, 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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
such as
RSA encryption
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
, which require the user to generate large
prime numbers
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
.
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
Failure rate is the frequency with which an engineered system or component fails, expressed in failures per unit of time. It is usually denoted by the Greek letter λ (lambda) and is often used in reliability engineering.
The failure rate of a ...
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
Cryptographic algorithms
Prime numbers
{{numtheory-stub