  Prime numbers play a very vital role in modern cryptography and especially
the difficulties involved in factoring numbers composed of product of two large
prime numbers have been put to use in many modern cryptographic designs. Thus,
the problem of distinguishing prime numbers from the rest is vital and
therefore there is a need to have efficient primality testing algorithms.
Although there had been many probabilistic algorithms for primality testing,
there wasn't a deterministic polynomial time algorithm until 2002 when Agrawal,
Kayal and Saxena came with an algorithm, popularly known as the AKS algorithm,
which could test whether a given number is prime or composite in polynomial
time. This project is an attempt at understanding the ingenious idea behind
this algorithm and the underlying principles of mathematics that is required to
study it. In fact, through out this project, one of the major objectives has
been to make it as much self contained as possible. Finally, the project
provides an implementation of the algorithm using Software for Algebra and
Geometry Experimentation (SAGE) and arrives at conclusions on how practical or
otherwise it is.
