Cryptography is the science of transmitting messages in a secured way. Naturally, it has become an important tool in this information age. It has already entered into our day-to-day lives through e-commerce. Needless to stress, it is important for the defense system of any country. We begin by discussing some private key cryptosystems and then move on to study public key cryptosystems. In a private key cryptosystem, the key is known to both the sender and the receiver while in a public key cryptosystem, which acts amidst a group of people, each member A of the group has a public key P A and a secret key S A. A computes his secret key and keeps it within himself. The keys P A and S A are inverses of each other. The security of the system rests on the fact that no person other than A or an intruder would be able to find out the secret key. Of the cryptosystems that we discuss, the Caesar cryptosystem and the affine cryptosystem are private key cryptosystems while the Diffie-Hellman, ElGamal and RSA cryptosystems are public key cryptosystems.
The most commonly applied public key cryptosystem is the RSA. It is built upon the premise that while multiplication of two large positive integers is easy when compared to the factorization of a very large composite number. This naturally leads to the problem of primality testing, that is, testing if a given large positive integer is prime or not. This problem was remaining open until 2002 when Agrawal, Saxena and Kayal came up with a polynomial time algorithm to test if a given positive integer is prime or not. In this chapter, we present this algorithm as also its proof. As far as we know, this is the first time that this proof is presented in a text.