Abstract:
Prime numbers are of the utmost importance in many applications and in particular cryptography. Firstly, number theory background is introduced in order to present the non-deterministic Solovay-Strassen primality test. Sec- ondly, the deterministic primality test discovered by Agrawal, Kayal and Sax- ena in 2002 is presented with the proofs following their original paper. Lastly, a remark will be made about the practical application of the deterministic algorithm versus using the non-deterministic algorithms in applications.
