ABSTRACT
In this chapter, the authors discuss the RSA Cryptosystem, which was the first example of a public-key cryptosystem to be discovered, along with related mathematical concepts including algorithms for factoring large integers. However, in practice, primality testing is still done mainly by using a randomized polynomial-time Monte Carlo algorithm such as the Solovay-Strassen algorithm or the Miller-Rabin algorithm, both of which are presented in this chapter. Although the Miller-Rabin algorithm is faster than the Solovay-Strassen algorithm, the authors first look at the Solovay-Strassen algorithm because it is easier to understand conceptually and because it involves some number-theoretic concepts that will be useful in later chapters of the book. The most obvious way to attack the RSA Cryptosystem is to attempt to factor the public modulus. One specific, well-known algorithm that has been widely used in practice is the Quadratic Sieve due to Pomerance.
