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.
Results: [to be completed at the end of the project.]