Page 258 - Discrete Mathematics and Its Applications

CH A P TER

4 Number Theory and Cryptography

4.1 Divisibility and he part of mathematics devoted to the study of the set of integers and their properties is
Modular Tknown as number theory. In this chapter we will develop some of the important concepts
Arithmetic of number theory including many of those used in computer science. As we develop number
theory, we will use the proof methods developed in Chapter 1 to prove many theorems.
4.2 Integer Repre-
sentations and We will first introduce the notion of divisibility of integers, which we use to introduce
Algorithms modular, or clock, arithmetic. Modular arithmetic operates with the remainders of integers
when they are divided by a fixed positive integer, called the modulus. We will prove many
4.3 Primes and important results about modular arithmetic which we will use extensively in this chapter.
Greatest Integers can be represented with any positive integer b greater than 1 as a base. In this
Common chapter we discuss base b representations of integers and give an algorithm for finding them.
Divisors In particular, we will discuss binary, octal, and hexadecimal (base 2, 8, and 16) representations.
We will describe algorithms for carrying out arithmetic using these representations and study
4.4 Solving
their complexity. These algorithms were the first procedures called algorithms.
Congruences
We will discuss prime numbers, the positive integers that have only 1 and themselves
4.5 Applications of as positive divisors. We will prove that there are infinitely many primes; the proof we give is
Congruences considered to be one of the most beautiful proofs in mathematics.We will discuss the distribution
4.6 Cryptography of primes and many famous open questions concerning primes. We will introduce the concept of
greatest common divisors and study the Euclidean algorithm for computing them.This algorithm
was first described thousands of years ago. We will introduce the fundamental theorem of
arithmetic, a key result which tells us that every positive integer has a unique factorization into
primes.
We will explain how to solve linear congruences, as well as systems of linear congruences,
which we solve using the famous Chinese remainder theorem. We will introduce the notion of
pseudoprimes, which are composite integers masquerading as primes, and show how this notion
can help us rapidly generate prime numbers.
This chapter introduces several important applications of number theory. In particular, we
will use number theory to generate pseudorandom numbers, to assign memory locations to
computer files, and to find check digits used to detect errors in various kinds of identification
numbers. We also introduce the subject of cryptography. Number theory plays an essentially
role both in classical cryptography, first used thousands of years ago, and modern cryptography,
which plays an essential role in electronic communication. We will show how the ideas we
develop can be used in cryptographical protocols, introducing protocols for sharing keys and for
sending signed messages. Number theory, once considered the purest of subjects, has become
an essential tool in providing computer and Internet security.

4.1 Divisibility and Modular Arithmetic

Introduction

The ideas that we will develop in this section are based on the notion of divisibility. Division of an
integer by a positive integer produces a quotient and a remainder.Working with these remainders
leads to modular arithmetic, which plays an important role in mathematics and which is used
throughoutcomputerscience.Wewilldiscusssomeimportantapplicationsofmodulararithmetic

237