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:
“Thus all probable reasoning is nothing but a species of sensation. ‘Tis not solely in poetry and music, we must follow our taste and sentiment, but likewise in philosophy, When I am convinc’d of any principle, ‘tis only an idea which strikes more strongly upon me. When I give the preference to one set of arguments above another, I do nothing but decide from my feeling concerning the superiority of their influence.”
—David Hume (1711–1776)
“And shall I prime my children, pray, to pray?”
—Gwendolyn Brooks (b. 1917)