| Primality testing and finding large prime numbers has significant applications to cryptography. In this thesis I will present a deterministic, polynomial time algorithm for determining if an integer is prime developed by Agrawal, Kayal, and Saxena. Here polynomial time means that there exists constants c,d such that the number of operations to determine if the given integer is prime is less than c logd n where n is the number we are testing. I will also do a short comparison of this algorithm to others both deterministic and probabilistic. |
