Primality test
A primality test is an
Simple methods
The simplest primality test is trial division: given an input number, , check whether it is
For example, consider the number 100, whose divisors are these numbers:
- 1, 2, 4, 5, 10, 20, 25, 50, 100.
When all possible divisors up to are tested, some divisors will be discovered twice. To observe this, consider the list of divisor pairs of 100:
- .
Products past are the reverse of products that appeared earlier. For example, and are the reverse of each other. Further, that of the two divisors, and . This observation generalizes to all : all divisor pairs of contain a divisor less than or equal to , so the algorithm need only search for divisors less than or equal to to guarantee detection of all divisor pairs.[1]
Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by the
For another example, consider how this algorithm determines the primality of 17. One has , and the only primes are 2 and 3. Neither divides 17, proving that 17 is prime. For a last example, consider 221. One has , and the primes are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that , proving that 221 is not prime.
In cases where it is not feasible to compute the list of primes , it is also possible to simply (and slowly) check all numbers between and for divisors. A rather simple optimization is to test divisibility by 2 and by just the odd numbers between 3 and , since divisibility by an even number implies divisibility by 2.
This method can be improved further. Observe that all primes greater than 3 are of the form for a nonnegative integer and . Indeed, every integer is of the form for a positive integer and . Since 2 divides , and , and 3 divides and , the only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for is to test whether is divisible by 2 or 3, then to check through all numbers of the form and which are . This is almost three times as fast as testing all numbers up to .
Generalizing further, all primes greater than (c primorial) are of the form for positive integers, , and
As grows, the fraction of coprime remainders to remainders decreases, and so the time to test decreases (though it still necessary to check for divisibility by all primes that are less than ). Observations analogous to the preceding can be applied recursively, giving the Sieve of Eratosthenes.
One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental against all known primes ). Then, before testing for primality with a large-scale method, can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.
A simple but very inefficient primality test uses Wilson's theorem, which states that is prime if and only if:
Although this method requires about modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.
Example code
Primality tests can be implemented in various ways. Here are examples in different programming languages:
Python
This test is in Python using the simple 6k ± 1 optimization mentioned earlier. More sophisticated methods described below are much faster for large n.
from math import isqrt
def is_prime(n: int) -> bool:
if n <= 3:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False
limit = isqrt(n)
for i in range(5, limit+1, 6):
if n % i == 0 or n % (i+2) == 0:
return False
return True
C, C++, C#, D
This test is in the
bool IsPrime(int n)
{
if (n == 2 || n == 3)
return true;
if (n <= 1 || n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
PHP
This test is in PHP using same optimization as above. Was orginally implemented by Mark Rogoyski in MathPHP library.
function isPrime(int $n): bool
{
if ($n <= 1) {
return false;
}
if ($n === 2 || $n === 3) {
return true;
}
if ($n % 2 === 0 || $n % 3 === 0) {
return false;
}
for ($i = 5; $i <= \sqrt($n); $i += 6) {
if ($n % $i === 0 || $n % ($i + 2) === 0) {
return false;
}
}
return true;
}
OCaml
This test is in OCaml using same optimization as above.
let is_prime n =
if n <= 1 then
false
else
(if n = 2 || n = 3 then
true
else
(if n mod 2 = 0 || n mod 3 = 0 then
false
else
let i = ref 5 in
while !i * !i <= n && n mod !i <> 0 && n mod (!i + 2) <> 0 do
i := !i + 6
done;
(!i * !i > n)
)
)
Rust
This test is in Rust using same optimization as above.
fn is_prime(n: i32) -> bool {
if n == 2 || n == 3 {
return true;
}
if n <= 1 || n % 2 == 0 || n % 3 == 0 {
return false;
}
(5..)
.step_by(6)
.take_while(|i| i * i <= n)
.all(|i| n % i != 0 && n % (i + 2) != 0)
}
Java
This test is in Java using the same optimization as above.
import java.util.*;
public static boolean isPrime(int n){
if (n <= 1)
return false;
if (n == 2 || n == 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i <= Math.sqrt(n); i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
JavaScript
This test is in JavaScript using the same optimization as above.
function isPrime(num) {
if (num == 2 || num == 3)
return true;
if (num <= 1 || num % 2 == 0 || num % 3 == 0)
return false;
for (let i = 5; i * i <= num ; i+=6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
R
This test is in R using the same optimization as above.
is.prime <- function(number) {
if (number <= 1) {
return (FALSE)
} else if (number <= 3) {
return (TRUE)
}
if (number %% 2 == 0 || number %% 3 == 0) {
return (FALSE)
}
i <- 5
while (i*i <= number) {
if (number %% i == 0 || number %% (i+2) == 0) {
return (FALSE)
}
i = i + 6
}
return (TRUE)
}
Dart
This test is in Dart using the same optimization as above.
checkIfPrimeNumber(number) {
if (number == 2 || number == 3) {
return 'true';
} else if (number <= 1 || number % 2 == 0 || number % 3 == 0) {
return 'false';
}
for (int i = 5; i * i <= number; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return 'false';
}
}
return 'true';
}
Free Pascal
This test is in Free Pascal using the same optimization as above.
function IsPrime(N: Int64):Boolean;
var
I: Int64;
begin
if ((N = 2) or (N = 3)) then
Exit(True);
if ((N <= 1) or ((N mod 2) = 0) or ((N mod 3) = 0)) then
Exit(False);
I := 5;
while (I * I <= N) do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then
Exit(False);
Inc(I, 6);
end;
Exit(True);
end;
Go
This test is in Go using the same optimization as above.
func IsPrime(num int) bool {
if num > 1 && num <= 3 {
return true
}
if num <= 1 || num%2 == 0 || num%3 == 0 {
return false
}
for i := 5; i*i <= num; i += 6 {
if num%i == 0 || num%(i+2) == 0 {
return false
}
}
return true
}
Haskell
This test is in Haskell using the same optimization as above.
isPrime :: Int -> Bool
isPrime = go $ 2 : 3 : scanl (+) 5 (cycle [2, 4])
where
go (p:ps) n
| p * p > n = True
| n `mod` p == 0 = False
| otherwise = go ps n
Zig This test is in Zig using the same optimization as above.
fn isPrime(n: u64) bool{
if(n == 2 or n == 3){
return true;
}
if(n < 1 or n % 2 == 0 or n % 3 == 0){
return false;
}
var i:u64 = 5;
while(i * i <= n) : (i += 6){
if(n % i == 0 or n % (i + 2) == 0){
return false;
}
}
return true;
}
Regular expression
The simple method can also be performed using a Regular expression by generating a string of n identical characters and running an expression of the form:
/^.?$|^(..+?)\1+$/
If the expression matches, the number is not a prime number.
The expression consists of two branches:
- The first branch matches 0 and 1.
- The second branch will check if any sequence of 2 or more characters exists that repeats a whole number of times, starting at the smallest sequence and working up. (The quantifier
+?
is a lazy quantifier, meaning it will try to match as few characters as possible, only increasing the size if no match is found using that value).
While this is a compact check, it executes the less efficient version where all possible divisors from 2 to n are checked, not stopping at .
Heuristic tests
These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all. The Fermat test and the Fibonacci test are simple examples, and they are very effective when combined. John Selfridge has conjectured that if p is an odd number, and p ≡ ±2 (mod 5), then p will be prime if both of the following hold:
- 2p−1 ≡ 1 (mod p),
- fp+1 ≡ 0 (mod p),
where fk is the k-th
In general, if p ≡ a (mod x2+4), where a is a quadratic non-residue (mod x2+4) then p should be prime if the following conditions hold:
- 2p−1 ≡ 1 (mod p),
- f(1)p+1 ≡ 0 (mod p),
f(x)k is the k-th
Selfridge,
Probabilistic tests
Probabilistic tests are more rigorous than heuristics in that they provide provable bounds on the probability of being fooled by a composite number. Many popular primality tests are probabilistic tests. These tests use, apart from the tested number n, some other numbers a which are chosen at random from some sample space; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of a; for two commonly used tests, for any composite n at least half the a's detect n's compositeness, so k repetitions reduce the error probability to at most 2−k, which can be made arbitrarily small by increasing k.
The basic structure of randomized primality tests is as follows:
- Randomly pick a number a.
- Check equality (corresponding to the chosen test) involving a and the given number n. If the equality fails to hold true, then n is a composite number and a is a witness for the compositeness, and the test stops.
- Get back to the step one until the required accuracy is reached.
After one or more iterations, if n is not found to be a composite number, then it can be declared probably prime.
Fermat primality test
The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It 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, then n is composite. If it is 1, then n may be prime.
If an−1 (modulo n) is 1 but n is not prime, then n is called a pseudoprime to base a. In practice, if an−1 (modulo n) is 1, then n is usually prime. But here is a counterexample: if n = 341 and a = 2, then
even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of [3]).
There are only 21853 pseudoprimes base 2 that are less than 2.5×1010 (see page 1005 of [3]). This means that, for n up to 2.5×1010, if 2n−1 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes.
Some composite numbers (
Miller–Rabin and Solovay–Strassen primality test
The Miller–Rabin primality test and Solovay–Strassen primality test are more sophisticated variants, which detect all composites (once again, this means: for every composite number n, at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers a are witnesses of compositeness of n). These are also compositeness tests.
The Miller–Rabin primality test works as follows: Given an integer n, choose some positive integer a < n. Let 2sd = n − 1, where d is odd. If
and
- for all
then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Miller–Rabin test is a strong probable prime test (see PSW[3] page 1004).
The Solovay–Strassen primality test uses another equality: Given an odd number n, choose some integer a < n, if
- , where is the Jacobi symbol,
then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Solovay–Strassen test is an Euler probable prime test (see PSW[3] page 1003).
For each individual value of a, the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if n = 1905 and a = 2, then the Miller-Rabin test shows that n is composite, but the Solovay–Strassen test does not. This is because 1905 is an Euler pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW[3]).
Frobenius primality test
The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is the Frobenius pseudoprimality test; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin.
The Frobenius test is a generalization of the Lucas probable prime test.
Baillie–PSW primality test
The Baillie–PSW primality test is a probabilistic primality test that combines a Fermat or Miller–Rabin test with a Lucas probable prime test to get a primality test that has no known counterexamples. That is, there are no known composite n for which this test reports that n is probably prime.[4][5] It has been shown that there are no counterexamples for n .
Other tests
If
Fast deterministic tests
Near the beginning of the 20th century, it was shown that a corollary of
In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by
Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ((log n)3) if Agrawal's conjecture is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false.[11] A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture,[14] may still be true.
Complexity
In computational complexity theory, the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing a factor.
In 1975, Vaughan Pratt showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in NP, and therefore in . See primality certificate for details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm[6] reduced the complexity to , which superseded Pratt's result.
The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP (quasi-polynomial time), which is not known to be comparable with the classes mentioned above.
Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P. However, PRIMES is not known to be P-complete, and it is not known whether it lies in classes lying inside P such as NC or L. It is known that PRIMES is not in AC0.[15]
Number-theoretic methods
Certain number-theoretic methods exist for testing whether a number is prime, such as the Lucas test and Proth's test. These tests typically require factorization of n + 1, n − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when the tested number n is known to have a special form.
The Lucas test relies on the fact that the multiplicative order of a number a modulo n is n − 1 for a prime n when a is a primitive root modulo n. If we can show a is primitive for n, we can show n is prime.
References
- ^ a b Riesel (1994) pp.2-3
- ^ John Selfridge#Selfridge's conjecture about primality testing.
- ^ .
- MR 0583518.
- S2CID 220055722.
- ^ ISBN 3-540-55308-8.
- arXiv:quant-ph/9508005.
- JFM 45.1250.02.
- ^ Weisstein, Eric W. "Pocklington's Theorem". MathWorld.
- .
- ^ .
- .
- ^ Carl Pomerance & Hendrik W. Lenstra (July 20, 2005). "Primality testing with Gaussian periods" (PDF).
- ^ Popovych, Roman (December 30, 2008). "A note on Agrawal conjecture" (PDF).
- ^ E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.
Sources
- ISBN 0-387-25282-7. Chapter 3: Recognizing Primes and Composites, pp. 109–158. Chapter 4: Primality Proving, pp. 159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp. 334–340.
- ISBN 0-201-89684-2.
- ISBN 0-262-03293-7.
- Zbl 0833.68049.
- Zbl 0821.11001.
External links
- Solovay-Strassen (computacion.cs.cinvestav.mx) at archive.today (archived 2012-12-20) – Implementation of the Solovay-Strassen primality test in Maple
- Distinguishing prime numbers from composite numbers, by D.J. Bernstein (cr.yp.to)
- The Prime Pages (primes.utm.edu)
- Lucas Primality Test with Factored N − 1 (MathPages.com) at the Library of Congress Web Archives (archived 2010-08-06)
- PRIMABOINCA is a research project that uses Internet-connected computers to search for a AKS algorithm).