Primes is in P

Goal:

For many purposes in cryptography it is essential to have `big' prime numbers; for instance, in the very widely used cryptosystem RSA (see lecture on Number Theory and Cryptography) one uses prime numbers having 2048 binary digits (i.e. of the size 2^2048,having 617 decimal digits). The question thus arises of how to find such big prime numbers. The answer is that one takes random numbers and tests if they are prime. One hence needs a fast test whether a given integer n is prime; such a test is called a primality test.

It is important to remark that a primality test only tests if an integer n is prime, it does not yield its decomposition into prime factors. This latter question is computationally very hard to solve (the security of RSA depends on this hardness). It has been known for some time that probabilistic primality testing is possible in time polynomial in the size of n (this means that the run time is bounded from above by a polynomial in \log(n), i.e. it can be bounded by \log(n)^m for some m \in N); for instance, the Miller-Rabin test (see Number Theory and Cryptography) achieves this. By probabilitistic primality testing one means that the result is true with a very high chance, but is not proved to be true.

It was a great surprise when in 2002 Agrawal, Kayal and Saxena found a primality test (called AKS-test) that runs in time polynomial in \log(n) (like Miller-Rabin) and yields proved results.

Literature:

Participants: Luca Notarnicola.

Supervisors: Gabor Wiese.

Difficulty level: Bachelor Thesis.

Results: Bachelor Thesis

FSCT -- University of Luxembourg