ABSTRACT
In this chapter, the authors discuss some basic concepts of number theory in the context of cryptography. They focus on the discussion of primality testing, factoring problem, quadratic residuosity, and discrete logarithm problem. Number theory and Cryptography are inextricably linked. People are generally curious to know that how many prime numbers actually exist. The Chinese Remainder Theorem is very useful in the field of cryptography. For example it is used in Rivest, Shamir and Adleman (RSA) cryptosystem to improve the efficiency of decryption procedure upto 4 times. Also, it is used for solving quadratic congruences and in represention of large integer into several integers. Number field sieve method was developed by John Pollard in 1988, and is considered to be an extremely quick factorization method which had been used for factoring RSA-130. Quadratic field sieve is an algorithm for solving factorization problem. It is known as the fastest algorithm after number field sieve for integers under 100 decimal digits.
