Algorithm with numbers


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s