**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:**

- Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004).
*PRIMES is in P*. Annals of Mathematics 160 (2): 781--793. doi:10.4007/annals.2004.160.781

**Participants:**
Luca Notarnicola.

**Supervisors:**
Gabor Wiese.

**Difficulty level:**
Bachelor Thesis.

**Results:**
Bachelor Thesis