Algorithmic Number Theory and Cryptography

Abstract

Primality testing and Integer factorization problem are two widely studied problems in Algorithmic Number Theory. Can we factorize integers in polynomial time is still an unsolved question. However, the Primality testing problem can be solved in polynomial time. RSA is the most widely used Public-key cryptosystem whose security is based on Integer factorization problem. Over past years researchers have studied various attacks on RSA cryptosystem, and it has been concluded that these attacks can be avoided if RSA is implemented securely. In this Thesis we have covered Primality testing algorithms, Factoring algorithms and Cryptanalysis of RSA.