Probable prime

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 "a""n" − 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".

An Euler probable prime to base "a" is an integer that is indicated prime by the somewhat stronger theorem that for any prime "p", "a"("p" − 1)/2 equals ("a"/"p") modulo "p", where ("a"/"p") is the Legendre symbol. An Euler probable prime which is composite is called an Euler-Jacobi pseudoprime to base "a".

This test may be improved by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Write "n" = "d" · 2"s" + 1, where "d" is odd. The number "n" is a strong probable prime (SPRP) to base "a" if one of the following conditions holds:: a^dequiv 1mod n: a^{dcdot 2^r}equiv -1mod nquadmbox{ for some }0leq rleq(s-1)A composite strong probable prime to base "a" is called a strong pseudoprime to base "a". Every strong probable prime to base "a" is also an Euler probable prime to the same base, but not vice versa.

Probable primality is a basis for efficient primality testing algorithms, which find application in cryptography. These algorithms are usually probabilistic in nature. The idea is that while there are composite probable primes to base "a" for any fixed "a", we may hope there exists some fixed "P"<1 such that for "any" given composite "n", if we choose "a" randomly the probability that "n" is pseudoprime to base "a" is at most "P". If we repeat this test "k" times, choosing a new "a" each time, the probability of "n" being pseudoprime to all the "a"s tested is hence at most "Pk", and as this decreases exponentially, only moderate "k" is required to make this probability negligibly small (compared to, for example, the probability of computer hardware error).

This is unfortunately false for weak probable primes, because there exist Carmichael numbers; but it is true for more refined notions of probable primality, such as strong probable primes ("P"=1/4, Miller-Rabin algorithm), orEuler probable primes ("P"=1/2, Solovay-Strassen algorithm).

Even when a deterministic primality proof is required, a useful first step is to test for probable primality. This can quickly eliminate (with certainty) most composites.

A PRP test is sometimes combined with a table of small pseudoprimes to quickly establish the primality of a given number smaller than some threshold.

ee also

* Euler-Jacobi pseudoprime
* Carmichael number
* Miller-Rabin primality test

External links

* [ The prime glossary - Probable prime]
* [ The PRP Top 10000 (the largest known probable primes)]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Prime gap — A prime gap is the difference between two successive prime numbers. The n th prime gap, denoted g n , is the difference between the ( n +1) th and the n th prime number, i.e.: g n = p n + 1 − p n .We have g 1 = 1, g 2 = g 3 = 2, and g 4 = 4. The… …   Wikipedia

  • Prime Minister of the United Kingdom — Infobox minister office border = parliamentary minister = prime title = Prime Minister jurisdiction = the United Kingdom of Great Britain and Northern Ireland incumbent = Gordon Brown tookoffice = 27 June 2007 appointed by = Elizabeth II monarch …   Wikipedia

  • Probable — Probabilité La probabilité (du latin probabilitas) est une évaluation du caractère probable d un évènement. En mathématiques, l étude des probabilités est un sujet de grande importance donnant lieu à de nombreuses applications. La probabilité d… …   Wikipédia en Français

  • Prime d'assurance — Pour les articles homonymes, voir prime. La prime d assurance est le prix que le preneur d’assurance doit payer pour pouvoir bénéficier de la couverture d’assurance en cas de sinistre. La prime se compose de trois parties: la partie risque, la… …   Wikipédia en Français

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • Wagstaff prime — A Wagstaff prime is a prime number p of the form:p=2^q+1}over 3}where q is another prime. Wagstaff primes are named after mathematician Samuel S. Wagstaff Jr., the prime pages credit François Morain for naming them in a lecture at the Eurocrypt… …   Wikipedia

  • Unique prime — In mathematics, a unique prime is a certain kind of prime number. A prime p ≠ 2, 5 is called unique if there is no other prime q such that the period length of the decimal expansion of its reciprocal, 1 / p , is equivalent to the period length of …   Wikipedia

  • Fibonacci prime — A Fibonacci prime is a Fibonacci number that is prime.The first Fibonacci primes are OEIS|id=A005478::2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, ....Known Fibonacci primesIt is not known if there are infinitely many… …   Wikipedia

  • Nombre Premier Probable — En Arithmétique modulaire, un nombre premier probable (NPP) est un entier qui satisfait à une condition qui est satisfaite aussi par tous les nombres premiers. Ces nombres premiers probables peuvent être composés (appelés pseudopremiers), ils… …   Wikipédia en Français

  • Nombre premier probable — En Arithmétique modulaire, un nombre premier probable (NPP) est un entier qui satisfait à une condition qui est satisfaite aussi par tous les nombres premiers. Ces nombres premiers probables peuvent être composés (appelés pseudopremiers), ils… …   Wikipédia en Français