Added to Favorites

Related Searches

Definitions

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.## See also

## External links

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)$

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 as tested is hence at most P^{k}, 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), or Euler 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.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday April 18, 2007 at 04:43:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday April 18, 2007 at 04:43:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.