MVEX01-16-08 Primality tests and the AKS primality test

Prime numbers are among the most studied and the most intriguing objects in Arithmetic.
They are not only interesting from a pure mathematical point of view, but they
appear ubiquitously in applications: they are used for encrypting and decrypting information
in a secure way - RSA principally, but also Elliptic curve cryptography - they are
used to implement generation of pseudo-random numbers, they appear in Cicadas life
cycle and in other applications to signal processing, controlling of low-order vibration
and even music practice.
 
The problem of testing whether a given number is prime might appear easy, but efficient
algorithms to do that in reasonable time have been discover only recently. The aim of
this project is to study the breakthrough by Agrawal, Kayal, and Saxena who developed
a deterministic algorithm that works in polynomial time. Despite the outstanding result,
the mathematical tools used in their proof are quite elementary and can be fully understood
by any willing undergraduate student. Some practical application and testing can
be implemented to test the validity of the algorithm.
 
Obs! För GU-studenter räknas projektet som ett projekt i Matematik (MMG900/MMG910).
 
Projektkod MVEX01-16-08
Gruppstorlek 3-4
Handledare Amos Turchet, 031-7723510 , tamos@chalmers.se
Examinator Maria Roginskaya
Institution Matematiska vetenskaper

Publicerad: to 29 okt 2015.