Probable Prime
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.
Fermat's test for compositeness, which is based on Fermat's little theorem, works as follows: given an integer n, choose some integer a coprime to n and calculate an − 1 modulo n. If the result is different from 1, n is composite. If it is 1, n may or may not be prime; n is then called a (weak) probable prime to base a.
Read more about Probable Prime: Properties, Variations
Famous quotes containing the words probable and/or prime:
“It makes me hate accepting things that are probable when they are held up before me as infallibly true. I prefer these words which tone down and modify the hastiness of our propositions: “Perhaps, In some sort, Some, They say, I think,” and the like.”
—Michel de Montaigne (1533–1592)
“Faith in reason as a prime motor is no longer the criterion of the sound mind, any more than faith in the Bible is the criterion of righteous intention.”
—George Bernard Shaw (1856–1950)