Probable prime

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite 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 that is not a multiple of n; (typically, we choose a in the range 1 < a < n − 1). Calculate a^{n − 1} modulo n. If the result is different from 1, then n is composite. If the result is 1, then n is likely to be prime; n is then called a probable prime to base a. A weak probable prime to base a is an integer that is a probable prime to base a, but which is not a strong probable prime to base a (see below).

For a fixed base a, it is unusual for a composite number to be a probable prime (that is, a pseudoprime) to that base. For example, up to 25 × 10⁹, there are 11,408,012,595 odd composite numbers, but only 21,853 pseudoprimes base 2.^[1]^{:p. 1005}

Properties

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.

Variations

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 $(\tfrac{a}{p})$ modulo p, where $(\tfrac{a}{p})$ is the Jacobi symbol. An Euler probable prime which is composite is called an Euler–Jacobi pseudoprime to base a. The smallest Euler-Jacobi pseudoprime to base 2 is 561 (see page 1004 of ^[1]). There are 11347 Euler-Jacobi pseudoprimes base 2 that are less than 25·10⁹ (page 1005 of ^[1]).

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^{d}\equiv 1{\pmod n},\;

a^{{d\cdot 2^{r}}}\equiv -1{\pmod n}{\text{ for some }}0\leq r\leq 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.

The smallest strong pseudoprime base 2 is 2047 (page 1004 of ^[1]). There are 4842 strong pseudoprimes base 2 that are less than 25·10⁹ (page 1005 of ^[1]).

There are also Lucas probable primes, which are based on Lucas sequences. A Lucas probable prime test can be used alone. The Baillie-PSW primality test combines a Lucas test with a strong probable prime test.

Example of SPRP

To test if 97 is probably prime:

Step 1: Find $d$ and $s$ for which $96=d\cdot 2^{s}$ , where $d$ is odd
- Beginning with $s=0$ , $d$ would be $96$
- Increasing $s$ , we see that $d=3$ and $s=5$ , since $96=3\cdot 2^{5}$
Step 2: Choose $a$ , $1<a<97-1$ . We will choose $2$
Step 3: Calculate $a^{d}{\pmod {n}}$ , i.e. $2^{3}{\pmod {97}}$ . Since it isn't congruent to $1{\pmod {97}}$ , we continue to test the next condition
Step 4: Calculate $2^{{3\cdot 2^{r}}}{\pmod {97}}$ for $0\leq r<s$ . If it is congruent to $96{\pmod {97}}$ , $97$ is probably prime. Otherwise, $97$ is definitely composite
- $r=0:2^{3}\equiv 8{\pmod {97}}$
- $r=1:2^{6}\equiv 64{\pmod {97}}$
- $r=2:2^{{12}}\equiv 22{\pmod {97}}$
- $r=3:2^{{24}}\equiv 96{\pmod {97}}$
Therefore, $97$ is probably prime.

External links

References

1 2 3 4 5 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. JSTOR 2006210. doi:10.1090/S0025-5718-1980-0572872-7.

Prime number classes
By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient
Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin
Patterns	Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)
By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Almost prime Semiprime Interprime
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 50 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229
List of prime numbers

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.