Primality test

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

Simple methods

The simplest primality test is trial division: given an input number, <math>n</math>, check whether it is divisible by any prime number between 2 and <math>\sqrt n</math> (i.e., whether the division leaves no remainder). If so, then <math>n</math> is composite. Otherwise, it is prime. All divisors <math>p \geq \sqrt n</math>, must have a divisor <math>\frac{n}{p} \leq \sqrt n</math>, and a prime divisor <math>q</math> of <math>\frac{n}{p}</math>, and therefore looking for prime divisors at most <math>\sqrt n</math> is sufficient.

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 <math>n</math> are tested, some divisors will be discovered twice. To observe this, consider the list of divisor pairs of 100:

:<math>1 \times 100, \; 2 \times 50, \; 4 \times 25, \; 5 \times 20, \; 10 \times 10, \; 20 \times 5, \; 25 \times 4, \; 50 \times 2, \; 100 \times 1</math>.

Products past <math>10 \times 10</math> are the reverse of products that appeared earlier. For example, <math>5 \times 20</math> and <math>20 \times 5</math> are the reverse of each other. Further, that of the two divisors, <math>5 \leq \sqrt{100} = 10</math> and <math>20 \geq \sqrt{100} = 10</math>. This observation generalizes to all <math>n</math>: all divisor pairs of <math>n</math> contain a divisor less than or equal to <math>\sqrt{n}</math>, so the algorithm need only search for divisors less than or equal to <math>\sqrt{n}</math> to guarantee detection of all divisor pairs. rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.

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 primality test and the Fibonacci test are simple examples, and they are 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 Fibonacci number. The first condition is the Fermat primality test using base 2.

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(x)p+1 ≡ 0 (mod p),

f(x)k is the k-th Fibonacci polynomial at x.

Selfridge, Pomerance and Wagstaff together offered $620 for a counterexample or proof that there is none, with the prize now due from the Number Theory Foundation.

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.

Multiple 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 as detect ns 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

: <math>2^{340} \equiv 1\pmod{341}</math>

even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of

There are only 21853 pseudoprimes base 2 that are less than 2.5 (see page 1005 of It has been shown that there are no counterexamples for n <math> < 2^{64}</math>.

Other tests

Leonard Adleman and Ming-Deh Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces a primality certificate, and thus can be used to prove that a number is prime. The algorithm is prohibitively slow in practice.

If quantum computers were available, primality could be tested asymptotically faster than by using classical computers. A combination of Shor's algorithm, an integer factorization method, with the Pocklington primality test could solve the problem in <math>O((\log n)^3 (\log\log n)^2 \log\log\log n)</math>.

Fast deterministic tests

Near the beginning of the 20th century, it was shown that a corollary of Fermat's little theorem could be used to test for primality. This resulted in the Pocklington primality test. However, as this test requires a partial factorization of n − 1 the running time was still quite slow in the worst case. The first deterministic primality test significantly faster than the naive methods was the cyclotomy test; its runtime can be proven to be O((log n)c log log log n), where n is the number to test for primality and c is a constant independent of n. A number of further improvements were made, but none could be proven to have polynomial running time. (Running time is measured in terms of the size of the input, which in this case is ~ log n, that being the number of bits needed to represent the number n.) The elliptic curve primality test can be proven to run in O((log n)6), if some conjectures on analytic number theory are true. Similarly, under the generalized Riemann hypothesis (which Miller, confusingly, calls the "extended Riemann hypothesis"), the deterministic Miller's test, which forms the basis of the probabilistic Miller–Rabin test, can be proved to run in Õ((log n)4). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because the implementation of these two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred.

In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. The AKS primality test runs in Õ((log n)12) (improved to Õ((log n)7.5) in the published revision of their paper), which can be further reduced to Õ((log n)6) if the Sophie Germain conjecture is true. Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally.

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. may still be true.

Recent research has proposed alternative deterministic approaches based on high-dimensional manifolds rather than modular arithmetic alone. The Absolute Ciaran-Genesis Conjecture (ACGC) and its expanded 32-dimensional Hyper-Genesis Framework (v14.0) suggest that primality can be modeled as a state of topological stability. By subjecting an integer to recursive endomorphisms across a 32-dimensional manifold, the framework attempts to identify "Lattice Fractures" as a deterministic indicator of compositeness, specifically aiming to resolve spectral resonance issues in Carmichael numbers.

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

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

Sources

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.

External links

– 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)
PRIMABOINCA is a research project that uses Internet-connected computers to search for a counterexample to some conjectures. The first conjecture (Agrawal's conjecture) was the basis for the formulation of the first deterministic prime test algorithm in polynomial time (AKS algorithm).