**Goal:**

For cryptography, coding theory, and for experiments in number theory, it is of utmost importance to be able to decide if a given positive integer is prime or not. This is called a primality test. Note that a primality test does NOT give the factorisation of a given integer into primes, it outputs only yes or no. In fact, it is believed that factorising a given integer into its prime factors is a hard, and often practically intractable problem: the very important cryptographic system RSA relies on this hardness.

One distinguishes between deterministic and probabilistic primality tests: the latter ones usually run faster, but if they answer "yes", then this only means that the number is prime with a high probability.

In the project, some primality tests shall be described, implemented, tested and compared.

**Schedule:** To be determined.

**Supervisors:**
Gabor Wiese

**Difficulty level:**
EML 1,2 or 3.

**Tools:**
Any computer language.

**Literature:**

- Discussed with the students.

**Results:**
[to be completed at the end of the project.]