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 was only too probable that among the half-converted Pagans and Jews, any rite, any form, would find favor, whilst yet unable to comprehend the spiritual character of Christianity.”
—Ralph Waldo Emerson (1803–1882)
“The prime purpose of being four is to enjoy being four—of secondary importance is to prepare for being five.”
—Jim Trelease (20th century)