## Primality testing

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.]