Deterministic and Probabilistic Approach in Primality Checking for RSA Algorithm

The RSA cryptosystem, invented by Ron Rivest, Adi Shamir and Len Adleman was first publicized in the August 1977 issue of Scientific American [1]. The security level of this algorithm very much depends on two large prime numbers [2]. In this paper two distinct approaches have been dealt with for primality checking. These are deterministic approach and probabilistic approach. For the deterministic approach, it has chosen modified trial division and for probabilistic approach, Miller-Rabin algorithm is considered. The different kinds of attacks on RSA and their remedy are also being discussed. This includes the chosen cipher text attacks, short private key exponent attack and frequency attack. Apart from these attacks, discussion has been made on how to choose the primes for the RSA algorithm. The time complexity has been demonstrated for the various algorithms implemented and compared with others. Finally the future modifications and expectations arising out of the current limitations have also been stated at the end.