One of the main themes of this chapter is the dramatic contrast between two ancient problems that at first seem very similar:
Factoring: Given a number N , express it as a product of its prime factors.
Primality: Given a number N , determine whether it is a prime.
Factoring is hard. Despite centuries of effort by some of the world’s smartest mathemati-
cians and computer scientists, the fastest methods for factoring a number N take time expo-nential in the number of bits of N .
On the other hand, we shall soon see that we can efficiently test whether N is prime!
And (it gets even more interesting) this strange disparity between the two intimately related problems, one very hard and the other very easy, lies at the heart of the technology that enables secure communication in today’s global information environment.
En route to these insights, we need to develop algorithms for a variety of computational
tasks involving numbers. We begin with basic arithmetic, an especially appropriate starting
point because, as we know, the word algorithms originally applied only to methods for these problems.
Download files here