A primality test is an algorithm for determining whether an input number is prime. It is important to note the difference between primality testing and integer factorization. As of 2008, factorization is a computationally hard problem, whereas primality testing is comparatively easy. Flowcharts are often used to graphically represent algorithms. ... In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... Prime decomposition redirects here. ... 2008 (MMVIII) is the current year, a leap year that started on Tuesday of the Anno Domini (or common era), in accordance to the Gregorian calendar. ...

Naïve methods

The simplest primality test is as follows: Given an input number n, we see if any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime. In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

Rather than testing all m up to n − 1, we need only test m up to : if n is composite then it can be factored into two values, at least one of which must be less than or equal to .

We can also improve the efficiency by skipping all even m except 2, since if any even number divides n then 2 does. We can further improve by observing that all primes are of the form 6k ± 1, with the only exceptions of 2 and 3. This is because all integers can be expressed as (6k + i) for some k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). We first test if n is divisible by 2 or 3, then we run through all the numbers of form 6k ± 1 . This is 3 times as fast as the previous method. In fact, all primes are of the form c#k + i for i < c# where i represents the numbers that are coprime to c#. In fact, as c → ∞ the number of values that c#k + i can take over a certain range decreases, and so the time to test n decreases. For this method, you must divide by all primes that are less than c. Observations analogous to the preceding can be applied recursively, giving the sieve of Eratosthenes. In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... For n ≥ 2, the primorial n# is the product of all prime numbers less than or equal to n. ... See: Recursion Recursively enumerable language Recursively enumerable set Recursive filter Recursive function Recursive set Primitive recursive function This is a disambiguation page — a list of pages that otherwise might share the same title. ... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ...

A good 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, say all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes). Then, before testing n for primality with a serious method, one first checks whether n is divisible by any prime from the list.

Probabilistic tests

Most 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 as; for two commonly used tests, for any composite n at least half the as 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. A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ...

The basic structure of randomized primality tests is as follows:

1. Randomly pick a number a.
2. Check some equality involving a and the given number n. If the equality fails to hold true, then n is a composite number, a is known as a witness for the compositeness, and the test stops.
3. Repeat from step 1 until the required certainty is achieved.

After several iterations, if n is not found to be a composite number, then it can be declared probably prime. A composite number is a positive integer which has a positive divisor other than one or itself. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... In number theory, a probable prime (PRP) is an integer that satisfies a condition also satisfied by all prime numbers. ...

The simplest probabilistic primality test is the Fermat primality test. It is only a heuristic test; some composite numbers (Carmichael numbers) will be declared "probably prime" no matter what witness is chosen. Nevertheless, it is sometimes used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographical algorithm. The Fermat primality test is a probabilistic test to determine if a number is composite or probably prime. ... In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence bn âˆ’ 1 ≡ 1 (mod n) for all integers b which are relatively prime to n (see modular arithmetic). ... In cryptography, RSA is an algorithm for public-key cryptography. ...

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). They are often the methods of choice, as they are much faster than other general primality tests. For high confidence, the Frobenius pseudoprimality test detects at least 99.987% of composites, though its runtime is typically three times that of Solovay-Strassen or Miller-Rabin. The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... The Solovay-Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. ... Wikipedia does not have an article with this exact name. ...

Leonard Adleman and Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces a certificate for primality, and thus can be used to prove that a number is prime. The algorithm is prohibitively slow in practice. Leonard Adleman Leonard Adleman (born December 31, 1945) is a theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. ... This article needs to be cleaned up to conform to a higher standard of quality. ...

Fast deterministic tests

The first deterministic primality test significantly faster than the naïve methods was the cyclotomy test; its runtime can be proven to be O((log n)^{clog log log n}), where n is the number to test for primality and c is a constant independent of n. In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ... The Adleman-Pomerance-Rumely primality test (APR) is a deterministic algorithm that tests if a positive integer is prime. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...

The elliptic curve primality test can be proven to run in O((log n)⁶), but only if some still unproven (but widely assumed to be true) statements of analytic number theory are used. It is one of the most often used deterministic tests in practice. This article needs to be cleaned up to conform to a higher standard of quality. ...

The implementation of these two methods is rather difficult, creating a risk of programming errors; this is one reason they are not preferred.

If the generalized Riemann hypothesis is assumed, the Miller-Rabin test can be turned into a deterministic version with runtime Õ((log n)⁴). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. The Riemann hypothesis is one of the most important conjectures in mathematics. ...

In 2002, Manindra Agrawal, Nitin Saxena and Neeraj Kayal described a new deterministic primality test, the AKS primality test, which they proved runs in Õ((log n)¹²), later improved to Õ((log n)^7.5). This was the first deterministic primality test with proven polynomial run-time. If a widely believed conjecture about the distribution of Sophie Germain primes is true, then it runs in Õ((log n)⁶). In practice, this algorithm is slower than probabilistic methods. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P. The... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. ...

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 coNP: its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing a factor. As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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 NP ∩ coNP. See primality certificate for details. Vaughan Pratt is Professor Emeritus of Computer Science at Stanford University. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. ...

The subsequent discovery of the Solovay-Strassen and Miller-Rabin algorithms put PRIMES in coRP. In 1992, the Adleman-Huang algorithm reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's result. In complexity theory, RP (randomized polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time in the input size If the correct answer is NO, it always returns NO If the correct answer is YES, then... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ...

The cyclotomy test of Adleman, Pomerance, and Rumely from 1983 put PRIMES in QP (quasi-polynomial time), which is not known to be comparable with the classes mentioned above. Carl Pomerance. ...

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 L or NC. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P. The... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ...

Number-theoretic methods

Certain number-theoretic methods exist for testing whether a number is prime, such as the Lucas-Lehmer 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. In mathematics, the Lucas-Lehmer test is a primality test for Mersenne numbers. ... Proths theorem states that if p is a prime Proth number ( of the form k * 2^n + 1 with k odd and k < 2^n ), then for some integer a, Where q = ( ( p-1)/2) This means that if you can find some number a, that multiplied it by...

The Lucas-Lehmer 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. In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with ak ≡ 1 (modulo n). ... A primitive root modulo n is a concept from modular arithmetic in number theory. ...

See also

• UBASIC for practical program (APRT-CLE).

This article needs to be cleaned up to conform to a higher standard of quality. ...

References

Richard E. Crandall is an American computer scientist who has made contributions to computational number theory. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Christos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, USA. He studied at the National Technical University of Athens (BS in Electrical Engineering, 1972) and at Princeton University (MS in Electrical Engineering, 1974 and PhD in Electrical Engineering and Computer Science, 1976). ... Manindra Agrawal (मणीन्द्र अग्रवाल) (born 20 May 1966 in Allahabad) is a professor of computer science at the Indian Institute of Technology, Kanpur. ... Neeraj Kayal graduated with a B.Tech from the Computer Science Department of the Indian Institute of Technology, Kanpur, India in 2002. ... Nitin Saxena is a Doctoral student at the Computer Science Department of the Indian Institute of Technology, Kanpur, India. ...

External links

• Distinguishing prime numbers from composite numbers, D.J. Bernstein
• The Prime Pages
• Big Primes Database
• Lucas Primality Test with Factored N-1 at MathPages

Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Flowcharts are often used to graphically represent algorithms. ... The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P. The... The Adleman-Pomerance-Rumely primality test (APR) is a deterministic algorithm that tests if a positive integer is prime. ... In number theory, the Baillie-PSW primality test is a probabilistic primality testing heuristic: it determines if a number is composite or a probable prime. ... Elliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number. ... The Fermat primality test is a probabilistic test to determine if a number is composite or probably prime. ... In computational number theory, the Lucas–Lehmer test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. ... In mathematics, the Lucas–Lehmer test is a primality test for Mersenne numbers. ... Proths theorem states that if p is a prime Proth number ( of the form k * 2^n + 1 with k odd and k < 2^n ), then for some integer a, Where q = ( ( p-1)/2) This means that if you can find some number a, that multiplied it by... In mathematics, Pépins test is a primality test, which can be used to determine whether a Fermat number is prime. ... The Solovay-Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. ... The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... Trial division is the simplest and easiest to understand of the integer factorization algorithms. ... In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. ... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ... In number theory, wheel factorization is a type of sieve where numbers are written around circles in a specific manner for the sieve to operate. ... Prime decomposition redirects here. ... In number theory, the continued fraction factorization method is an integer factorization algorithm. ... In number theory, Dixons factorization method (also Dixons algorithm) is a general-purpose integer factorization algorithm. ... The Lenstra elliptic curve factorization or the elliptic curve factorization method (ECM) is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. ... Pollards rho algorithm is a special-purpose integer factorization algorithm. ... Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ... In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm invented by H. C. Williams. ... The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). ... In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. ... The special number field sieve (SNFS) is a special-purpose integer factorization algorithm. ... In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ... With Fermats factoring method, one tries to represent an odd integer as the difference of two squares: . That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Furthermore, each odd number has such a representation. ... Input: N, the integer to be factored, which must be neither a prime number nor a perfect square. ... Trial division is the simplest and easiest to understand of the integer factorization algorithms. ... Shors algorithm is a quantum algorithm for factoring an integer N in O((log N)3) time and O(log N) space, named after Peter Shor. ... It has been suggested that this article or section be merged into Egyptian mathematics. ... Aryabhata algorithm is an algorithm to solve indeterminate Diophantine equations and for residue arithmetic. ... The binary GCD algorithm is an algorithm which computes the greatest common divisor of two positive integers. ... The Chakravala method is a cyclic algorithm to solve quadratic integer equations. ... In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in Bézouts identity (Typically either x or y is negative). ... An integer relation between a set of real numbers x1, x2, ..., xn is a set of integers a1, a2, ..., an, not all 0, such that An integer relation algorithm is an algorithm for finding integer relations. ... In number theory (a branch of mathematics), the integer square root (isqrt) of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n, For example, because and . ... Modular exponentiation is a type of exponentiation performed over a modulus. ... The Shanks-Tonelli algorithm is used within modular arithmetic to solve a congruence of the form where n is a quadratic residue (mod p), and is prime; typically, . When , it is much more efficient to use the following identity: . Shanks-Tonelli cannot be used for composite moduli, which is a... In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ...