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 is probable that in a fit of generosity the men of the United States would have enfranchised its women en masse; and the government now staggering under the ballots of ignorant, irresponsible men, must have gone down under the additional burden of the votes which would have been thrown upon it, by millions of ignorant, irresponsible women.”
—Jane Grey Swisshelm (1815–1884)
“By whatever means it is accomplished, the prime business of a play is to arouse the passions of its audience so that by the route of passion may be opened up new relationships between a man and men, and between men and Man. Drama is akin to the other inventions of man in that it ought to help us to know more, and not merely to spend our feelings.”
—Arthur Miller (b. 1915)