accessible to students who have mastered the material in this book.

Note that while continued fractions are not discussed, the closely related

problem of “rational reconstruction” is covered, along with a number of in-

teresting applications (which could also be solved using continued fractions).

Using the text. Here are a few tips on using the text.

• There are a few sections that are marked with a “(—),” indicating

that the material covered in that section is a bit technical, and is not

needed elsewhere.

• There are many examples in the text. These form an integral part of

the text, and should not be skipped.

• There are a number of exercises in the text that serve to reinforce,

as well as to develop important applications and generalizations of,

the material presented in the text. In solving exercises, the reader is

free to use any previously stated results in the text, including those

in previous exercises. However, except where otherwise noted, any

result in a section marked with a “(—),” or in §5.5, need not and

should not be used outside the section in which it appears.

• There is a very brief “Preliminaries” chapter, which ¬xes a bit of

notation and recalls a few standard facts. This should be skimmed

over by the reader.

• There is an appendix that contains a few useful facts; where such a

fact is used in the text, there is a reference such as “see §An,” which

refers to the item labeled “An” in the appendix.

Feedback. I welcome comments on the book (suggestions for improvement,

error reports, etc.) from readers. Please send your comments to

victor@shoup.net.

Preface xiii

There is also web site where further material and information relating to

the book (including a list of errata and the latest electronic version of the

book) may be found:

www.shoup.net/ntb.

Acknowledgments. I would like to thank a number of people who vol-

unteered their time and energy in reviewing one or more chapters: Sid-

dhartha Annapureddy, John Black, Carl Bosley, Joshua Brody, Jan Ca-

menisch, Ronald Cramer, Alex Dent, Nelly Fazio, Mark Giesbrecht, Stuart

Haber, Alfred Menezes, Antonio Nicolosi, Roberto Oliveira, and Louis Sal-

vail. Thanks to their e¬orts, the “bug count” has been signi¬cantly reduced,

and the readability of the text much improved. I am also grateful to the

National Science Foundation for their support provided under grant CCR-

0310297. Thanks to David Tranah and his colleagues at Cambridge Univer-

sity Press for their progressive attitudes regarding intellectual property and

open access.

New York, January 2005 Victor Shoup

Preliminaries

We establish here a few notational conventions used throughout the text.

Arithmetic with ∞

We shall sometimes use the symbols “∞” and “’∞” in simple arithmetic

expressions involving real numbers. The interpretation given to such ex-

pressions is the usual, natural one; for example, for all real numbers x, we

have ’∞ < x < ∞, x + ∞ = ∞, x ’ ∞ = ’∞, ∞ + ∞ = ∞, and

(’∞) + (’∞) = ’∞. Some such expressions have no sensible interpreta-

tion (e.g., ∞ ’ ∞).

Logarithms and exponentials

We denote by log x the natural logarithm of x. The logarithm of x to the

base b is denoted logb x.

We denote by ex the usual exponential function, where e ≈ 2.71828 is the

base of the natural logarithm. We may also write exp[x] instead of ex .

Sets and relations

We use the symbol … to denote the empty set. For two sets A, B, we use the

notation A ⊆ B to mean that A is a subset of B (with A possibly equal to

B), and the notation A B to mean that A is a proper subset of B (i.e.,

A ⊆ B but A = B); further, A ∪ B denotes the union of A and B, A © B

the intersection of A and B, and A \ B the set of all elements of A that are

not in B.

For sets S1 , . . . , Sn , we denote by S1 — · · · — Sn the Cartesian product

xiv

Preliminaries xv

of S1 , . . . , Sn , that is, the set of all n-tuples (a1 , . . . , an ), where ai ∈ Si for

i = 1, . . . , n.

We use the notation S —n to denote the Cartesian product of n copies of

a set S, and for x ∈ S, we denote by x—n the element of S —n consisting of

n copies of x. (We shall reserve the notation S n to denote the set of all nth

powers of S, assuming a multiplication operation on S is de¬ned.)

Two sets A and B are disjoint if A © B = …. A collection {Ci } of sets is

called pairwise disjoint if Ci © Cj = … for all i, j with i = j.

A partition of a set S is a pairwise disjoint collection of non-empty

subsets of S whose union is S. In other words, each element of S appears

in exactly one subset.

A binary relation on a set S is a subset R of S — S. Usually, one writes

a ∼ b to mean that (a, b) ∈ R, where ∼ is some appropriate symbol, and

rather than refer to the relation as R, one refers to it as ∼.

A binary relation ∼ on a set S is called an equivalence relation if for

all x, y, z ∈ S, we have

• x ∼ x (re¬‚exive property),

• x ∼ y implies y ∼ x (symmetric property), and

• x ∼ y and y ∼ z implies x ∼ z (transitive property).

If ∼ is an equivalence relation on S, then for x ∈ S one de¬nes the set

[x] := {y ∈ S : x ∼ y}. Such a set [x] is an equivalence class. It follows

from the de¬nition of an equivalence relation that for all x, y ∈ S, we have

• x ∈ [x], and

• either [x] © [y] = … or [x] = [y].

In particular, the collection of all distinct equivalence classes partitions the

set S. For any x ∈ S, the set [x] is called the the equivalence class

containing x, and x is called a representative of [x].

Functions

For any function f from a set A into a set B, if A ⊆ A, then f (A ) :=

{f (a) ∈ B : a ∈ A } is the image of A under f , and f (A) is simply referred

to as the image of f ; if B ⊆ B, then f ’1 (B ) := {a ∈ A : f (a) ∈ B } is the

pre-image of B under f .

A function f : A ’ B is called one-to-one or injective if f (a) = f (b)

implies a = b. The function f is called onto or surjective if f (A) = B.

The function f is called bijective if it is both injective and surjective; in

this case, f is called a bijection. If f is bijective, then we may de¬ne the

xvi Preliminaries

inverse function f ’1 : B ’ A, where for b ∈ B, f ’1 (b) is de¬ned to be

the unique a ∈ A such that f (a) = b.

If f : A ’ B and g : B ’ C are functions, we denote by g —¦ f their

composition, that is, the function that sends a ∈ A to g(f (a)) ∈ C. Function

composition is associative; that is, for functions f : A ’ B, g : B ’ C,

and h : C ’ D, we have (h —¦ g) —¦ f = h —¦ (g —¦ f ). Thus, we can simply

write h —¦ g —¦ f without any ambiguity. More generally, if we have functions

fi : Ai ’ Ai+1 for i = 1, . . . , n, where n ≥ 2, then we may write their

composition as fn —¦ · · · —¦ f1 without any ambiguity. As a special case of this,

if Ai = A and fi = f for i = 1, . . . , n, then we may write fn —¦ · · · —¦ f1 as

f n . It is understood that f 1 = f , and that f 0 is the identity function on A.

If f is a bijection, then so is f n for any non-negative integer n, the inverse

function of f n being (f ’1 )n , which one may simply write as f ’n .

Binary operations

A binary operation on a set S is a function from S — S to S, where the

value of the function at (a, b) ∈ S — S is denoted a b.

A binary operation on S is called associative if for all a, b, c ∈ S, we

have (a b) c = a (b c). In this case, we can simply write a b c without

any ambiguity. More generally, for a1 , . . . , an ∈ S, where n ≥ 2, we can

write a1 · · · an without any ambiguity.

A binary operation on S is called commutative if for all a, b ∈ S,

we have a b = b a. If the binary operation is both associative and

commutative, then not only is the expression a1 · · · an unambiguous, but

its value remains unchanged even if we re-order the ai .