ABSTRACT
In the first two chapters we studied a few basic properties of the integerswithout which we couldn’t prove much, and two fundamental algorithmswithout which we couldn’t compute much. The subject of this chapter, however, is more visibly concerned with our ultimate goal: the RSA cryptosystem. In deed, to make sure that our implementation of the RSA is secure we must be able to choose large prime numbers: two for each user. This is the problem that we begin to address in this chapter. First we consider primes obtained from polynomial, exponential, and primorial formulae. An important consequence of our study of the primorial formula will be a proof that there exist infinitely many prime numbers. The chapter ends with a discussion of the sieve of Erathostenes, which is the oldest known method for finding primes, and also the grandparent of all modern sieves.
