Page 267 - Discrete Mathematics and Its Applications

246 4 / Number Theory and Cryptography

As mentioned in Section 3.1, the term algorithm originally referred to procedures for per-
forming arithmetic operations using the decimal representations of integers. These algorithms,
adapted for use with binary representations, are the basis for computer arithmetic. They provide
good illustrations of the concept of an algorithm and the complexity of algorithms. For these
reasons, they will be discussed in this section.
We will also introduce an algorithm for finding a div d and a mod d where a and d are
integers with d> 1. Finally, we will describe an efficient algorithm for modular exponentiation,
which is a particularly important algorithm for cryptography, as we will see in Section 4.6.

Representations of Integers

In everyday life we use decimal notation to express integers. For example, 965 is used to denote
2
9 · 10 + 6 · 10 + 5. However, it is often convenient to use bases other than 10. In particular,
computers usually use binary notation (with 2 as the base) when carrying out arithmetic, and
octal (base 8) or hexadecimal (base 16) notation when expressing characters, such as letters or
digits. In fact, we can use any integer greater than 1 as the base when expressing integers. This
is stated in Theorem 1.

THEOREM 1 Let b be an integer greater than 1. Then if n is a positive integer, it can be expressed uniquely
in the form
k
n = a k b + a k−1 b k−1 + ··· + a 1 b + a 0 ,

where k is a nonnegative integer, a 0 ,a 1 ,...,a k are nonnegative integers less than b, and
a k = 0.

A proof of this theorem can be constructed using mathematical induction, a proof method that
is discussed in Section 5.1. It can also be found in [Ro10]. The representation of n given in
Theorem 1 is called the base b expansion of n. The base b expansion of n is denoted by
2
(a k a k−1 ...a 1 a 0 ) b . For instance, (245) 8 represents 2 · 8 + 4 · 8 + 5 = 165. Typically, the sub-
script 10 is omitted for base 10 expansions of integers because base 10, or decimal expansions,
are commonly used to represent integers.

BINARY EXPANSIONS Choosing 2 as the base gives binary expansions of integers. In
binary notation each digit is eithera0ora1.In other words, the binary expansion of an
integer is just a bit string. Binary expansions (and related expansions that are variants of binary
expansions) are used by computers to represent and do arithmetic with integers.

EXAMPLE 1 What is the decimal expansion of the integer that has (1 0101 1111) 2 as its binary expansion?

Solution: We have

5
8
7
6
(1 0101 1111) 2 = 1 · 2 + 0 · 2 + 1 · 2 + 0 · 2 + 1 · 2 4
0
1
2
3
+ 1 · 2 + 1 · 2 + 1 · 2 + 1 · 2 = 351. ▲
OCTAL AND HEXADECIMAL EXPANSIONS Among the most important bases in com-
puter science are base 2, base 8, and base 16. Base 8 expansions are called octal expansions and
base 16 expansions are hexadecimal expansions.