Prime test
A prime number test is a mathematical process used to determine whether or not a given number is prime .
Practical use
In practice, primality tests are used in particular for asymmetric encryption methods in cryptography . Algorithms like RSA require prime numbers in the order of magnitude of around 1000 digits in dual representation. So it is impossible to calculate all of these and save them in a list for easy access when needed. The pre-calculation of a subset is also questionable for security reasons, since the list could fall into the hands of attackers. Instead of using a known prime number, the algorithm guesses (with a few tricks) an “arbitrary” number and uses a prime number test to determine as quickly as possible whether this is actually prime.
Since "real" primality tests take too long for numbers of this size, a Monte Carlo algorithm is usually used, with which in reality it cannot be determined with absolute certainty whether the given number is a prime number (one also speaks of probabilistic primality tests ). However, the probability of mistaking a composite number for a prime number can be made as small as desired. Using a non-prime number as a cryptographic key would mean insecure encryption, but if the likelihood of this being a billion times lower than that of the sender and recipient of the message being struck by lightning at the same time, this risk is accepted, which is otherwise very much to be able to use secure encryption methods.
Known primality test procedures
There are numerous approaches to primality tests:
Trial division
The simplest primality test is the trial division. Here, one by one, to try whether the number by one of the prime numbers to be divided. If not, then it is prime. In practice, the trial division is only used for small to about a million . Other methods are more efficient for larger ones.
Sieve of Eratosthenes
The Sieve of Eratosthenes is an algorithm that generates a list of prime numbers. Since this list contains all prime numbers up to a freely selectable limit, it can be used for a prime number test. To do this, one checks whether the transferred number is in the list. This procedure is too time-consuming for large numbers and therefore cannot be used as a prime number test.
Atkin sieve
Atkin's sieve is a fast, modern algorithm for determining all prime numbers up to a given limit. It is an optimized version of the ancient sieve of Eratosthenes. The performance is with a small limit of z. B. 100 a little slower than with the sieve of Eratosthenes, but the larger the limit, the greater the time advantage compared to the old sieving method.
Probabilistic primality tests
The following primality tests - sorted in increasing strength - are based on Fermat's little theorem and its conclusions:
| Prime test | based on | Type of occurring pseudoprimes |
| Fermatscher primality test | little Fermatsch sentence | Fermatsche pseudoprimes |
| Solovay Strassen test | Set of Euler and Jacobi symbol | Euler's pseudoprimes |
| Miller-Rabin test | Miller's theorem | strong pseudoprimes |
The Miller-Rabin test is a probabilistic prime number test with an acceptable duration. For certain ranges of natural numbers it is known how many of the first prime numbers have to be used as bases in order to even make a reliable statement, i.e. to be able to use the algorithm deterministically (see episode A014233 in OEIS ).
Further primality tests based on Fermat's little theorem
- Lucas test and the more specific Pépin test for checking Fermat numbers
- Lucas-Lehmer test for checking Mersenne prime numbers
- The APRCL test, which in 1980 by mathematicians Leonard A dleman , Carl P omerance , Robert R umely , Henri C. heights and Hendrik W. L coastal road Jr. was developed and named after the initials of the inventor, is by turning off the Fermat Pseudoprimes a significant improvement of Fermat's primality test.
AKS method
The AKS method is a polynomial time primality test that was found in 2002 by Manindra Agrawal , Neeraj Kayal and Nitin Saxena and named after them.
Primality tests in complexity theory
The problem underlying the prime number test, determining whether a number is prime, is called PRIMES in computer science . Until 2002 it was hoped that complexity theory would provide new insights into the P-NP problem . If P ≠ NP holds, then by Ladner's theorem there must be a problem in NP \ P which is not NP-complete . PRIMES was considered a potential candidate for such a problem.
This was because PRIMES is in the complexity class NP as well as in the complexity class co-NP , and therefore could not be NP-complete (under the common assumption that P ≠ NP). However, no non-probabilistic solution algorithm with polynomial running time was known. Therefore it was questionable whether PRIMES is also in the P complexity class .
In 2002, however, Agrawal, Kayal and Saxena found such a polynomial prime number test with the AKS prime number test. This answered the long open question of whether PRIMES is in P. However, this did not provide any further insight into the P-NP problem.
Web links
- DJ Bernstein: Distinguishing prime numbers from composite numbers. An overview of various primality test methods.
- Online prime checker. Tests numbers with up to 15 decimal places (server side).
Individual evidence
- ↑ See Henri Cohen; Hendrik W. Lenstra, Jr .: Primality testing and Jacobi sums. In: Mathematics of Computation 42 (1984), No. 165, pp. 297-330.
- ↑ a b Manindra Agrawal, Neeraj Kayal, Nitin Saxena: Primes is in P . In: Annals of Mathematics . 160, No. 2, 2004, pp. 781-793. doi : 10.4007 / annals.2004.160.781 .
- ^ Richard E. Ladner: On the structure of polynomial time reducibility. In: Journal of the ACM. Vol. 22, No. 1, 1975, pp. 151-171, Corollary 1.1., ACM entry.