Primality test
A primality test is a mathematical procedure to determine whether a given number is a prime number or not.
Practical Application
In practice primality tests are used in particular for asymmetric encryption method in cryptography. Algorithms such as RSA primes need in the order of about 1,000 jobs in dual representation. It is therefore impossible to calculate all these and store them in a list to easily access it when necessary. The prediction of a subset is questionable for safety reasons, because the list attackers could fall into the hands. Instead of using a prime number, the algorithm advises ( with a few tricks ) an " arbitrary " number and, with the help of a prime number such tests as quickly as possible, whether it is really prime.
Since "real" primality tests take too long for numbers of this size, a Monte Carlo algorithm is commonly used in reality can not be determined with absolute certainty with whether the given number is prime ( also referred to as probabilistic primality tests ). However, it may likely to hold a composite number incorrectly for a prime number, be made arbitrarily small. Although the use of a non- prime number would mean as cryptographic keys an insecure encryption, but if the probability is billions of times smaller than the one that the sender and the message receiver are taken simultaneously by lightning, this risk is accepted to the otherwise very to use secure encryption method.
Known primality testing method
There are numerous approaches for primality testing:
Trial division
The simplest primality test is the trial division. This one tests one after the other, whether the number is by one of the prime numbers between 2 and divisible. If they are not, then is prime. The trial division is much too complicated, so it does not come into practice as a primality test used.
Sieve of Eratosthenes
The Sieve of Eratosthenes is an algorithm that generates a list of prime numbers. Since this list up to an arbitrary boundary contains all prime numbers, it can be used for a primality test. One checks as to whether the given number is in the list. Also, this method is too expensive for large numbers and therefore can not be used as a primality test.
Sieve of Atkin
The sieve of Atkin is a fast, modern algorithm for determining all prime numbers up to a specified limit. It is an optimized version of the ancient Sieve of Eratosthenes. The performance is at a small limit of eg 100, the greater was somewhat slower than in the sieve of Eratosthenes, but the larger the limit the time advantage over the old screening method.
Probabilistic primality testing
The following - sorted in ascending strength - primality tests based on the small Fermat's theorem and conclusions from this:
The Miller -Rabin test is a probabilistic primality test with acceptable runtime. For certain areas of natural numbers is well known how many of the first prime numbers must be used as bases to even make a definite statement, to so use the algorithm deterministically (see A014233 in OEIS sequence ).
More primality tests that are based on the small Fermat's theorem
- Lucas- test, and the specific test for testing Pepin Fermat numbers
- Lucas- Lehmer test for testing Mersenne primes
- APRCL test ( the name consists of the initials of the mathematician Leonard Adleman, Carl Pomerance, Robert Rumely, Henri Cohen and Hendrik W. Lenstra Jr ), a further improvement of the Fermat primality tests
AKS method
The AKS primality test method is a polynomial, which was found in 2002 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena and named after them.
Primality tests in complexity theory
The primality test the underlying problem, determine whether a number is prime is called in computer science as PRIMES. By the year 2002 it was hoped that in the complexity theory of their new findings with respect to the P- NP problem. If P ≠ NP, there must be a problem in NP \ P to the set of Ladner, which is not NP -complete. PRIMES was considered a potential candidate for such a problem.
This was because PRIMES lies both in the complexity class NP and in the complexity class co-NP, and therefore could not be NP-complete (under the common assumption that P ≠ NP). But you did not know any non- probabilistic polynomial- time solution algorithm. Therefore, it was questionable whether PRIMES is in the complexity class P.
2002, but with the AKS primality test found by Agrawal, Kayal and Saxena such a polynomial primality test. This was the long -time open question whether PRIMES is in P, answered. However, this did not yield any further insight to the P - NP problem.