## Contents

Preface page x

Preliminaries xiv

1 Basic properties of the integers 1

1.1 Divisibility and primality 1

1.2 Ideals and greatest common divisors 5

1.3 Some consequences of unique factorization 10

2 Congruences 15

2.1 Equivalence relations 15

2.2 Definitions and basic properties of congruences 16

2.3 Solving linear congruences 19

2.4 The Chinese remainder theorem 22

2.5 Residue classes 25

2.6 Euler’s phi function 31

2.7 Euler’s theorem and Fermat’s little theorem 32

2.8 Quadratic residues 35

2.9 Summations over divisors 45

3 Computing with large integers 50

3.1 Asymptotic notation 50

3.2 Machine models and complexity theory 53

3.3 Basic integer arithmetic 55

3.4 Computing in Zn 64

3.5 Faster integer arithmetic () 69

3.6 Notes 71

4 Euclid’s algorithm 74

4.1 The basic Euclidean algorithm 74

4.2 The extended Euclidean algorithm 77

4.3 Computing modular inverses and Chinese remaindering 82

4.4 Speeding up algorithms via modular computation 84

4.5 An eective version of Fermat’s two squares theorem 86

4.6 Rational reconstruction and applications 89

4.7 The RSA cryptosystem 99

4.8 Notes 102

5 The distribution of primes 104

5.1 Chebyshev’s theorem on the density of primes 104

5.2 Bertrand’s postulate 108

5.3 Mertens’ theorem 110

5.4 The sieve of Eratosthenes 115

5.5 The prime number theorem . . . and beyond 116

5.6 Notes 124

6 Abelian groups 126

6.1 Definitions, basic properties, and examples 126

6.2 Subgroups 132

6.3 Cosets and quotient groups 137

6.4 Group homomorphisms and isomorphisms 142

6.5 Cyclic groups 153

6.6 The structure of finite abelian groups () 163

7 Rings 166

7.1 Definitions, basic properties, and examples 166

7.2 Polynomial rings 176

7.3 Ideals and quotient rings 185

7.4 Ring homomorphisms and isomorphisms 192

7.5 The structure of Zn

203

8 Finite and discrete probability distributions 207

8.1 Basic definitions 207

8.2 Conditional probability and independence 213

8.3 Random variables 221

8.4 Expectation and variance 233

8.5 Some useful bounds 241

8.6 Balls and bins 245

8.7 Hash functions 252

8.8 Statistical distance 260

8.9 Measures of randomness and the leftover hash lemma () 266

8.10 Discrete probability distributions 270

8.11 Notes 275

9 Probabilistic algorithms 277

9.1 Basic definitions 278

9.2 Generating a random number from a given interval 285

9.3 The generate and test paradigm 287

9.4 Generating a random prime 292

9.5 Generating a random non-increasing sequence 295

9.6 Generating a random factored number 298

9.7 Some complexity theory 302

9.8 Notes 304

10 Probabilistic primality testing 306

10.1 Trial division 306

10.2 The Miller–Rabin test 307

10.3 Generating random primes using the Miller–Rabin test 311

10.4 Factoring and computing Euler’s phi function 320

10.5 Notes 324

11 Finding generators and discrete logarithms in Zp

327

11.1 Finding a generator for Zp

327

11.2 Computing discrete logarithms in Zp

329

11.3 The Die–Hellman key establishment protocol 334

11.4 Notes 340

12 Quadratic reciprocity and computing modular square roots 342

12.1 The Legendre symbol 342

12.2 The Jacobi symbol 346

12.3 Computing the Jacobi symbol 348

12.4 Testing quadratic residuosity 349

12.5 Computing modular square roots 350

12.6 The quadratic residuosity assumption 355

12.7 Notes 357

13 Modules and vector spaces 358

13.1 Definitions, basic properties, and examples 358

13.2 Submodules and quotient modules 360

13.3 Module homomorphisms and isomorphisms 363

13.4 Linear independence and bases 367

13.5 Vector spaces and dimension 370

14 Matrices 377

14.1 Basic definitions and properties 377

14.2 Matrices and linear maps 381

14.3 The inverse of a matrix 386

14.4 Gaussian elimination 388

14.5 Applications of Gaussian elimination 392

14.6 Notes 398

15 Subexponential-time discrete logarithms and factoring 399

15.1 Smooth numbers 399

15.2 An algorithm for discrete logarithms 400

15.3 An algorithm for factoring integers 407

15.4 Practical improvements 414

15.5 Notes 418

16 More rings 421

16.1 Algebras 421

16.2 The field of fractions of an integral domain 427

16.3 Unique factorization of polynomials 430

16.4 Polynomial congruences 435

16.5 Minimal polynomials 438

16.6 General properties of extension fields 440

16.7 Formal derivatives 444

16.8 Formal power series and Laurent series 446

16.9 Unique factorization domains () 451

16.10 Notes 464

17 Polynomial arithmetic and applications 465

17.1 Basic arithmetic 465

17.2 Computing minimal polynomials in F[X]=(f)(I) 468

17.3 Euclid’s algorithm 469

17.4 Computing modular inverses and Chinese remaindering 472

17.5 Rational function reconstruction and applications 474

17.6 Faster polynomial arithmetic () 478

17.7 Notes 484

18 Linearly generated sequences and applications 486

18.1 Basic definitions and properties 486

18.2 Computing minimal polynomials: a special case 490

18.3 Computing minimal polynomials: a more general case 492

18.4 Solving sparse linear systems 497

18.5 Computing minimal polynomials in F[X]=(f)(II) 500

18.6 The algebra of linear transformations () 501

18.7 Notes 508

19 Finite fields 509

19.1 Preliminaries 509

19.2 The existence of finite fields 511

19.3 The subfield structure and uniqueness of finite fields 515

19.4 Conjugates, norms and traces 516

20 Algorithms for finite fields 522

20.1 Tests for and constructing irreducible polynomials 522

20.2 Computing minimal polynomials in F[X]=(f)(III) 525

20.3 Factoring polynomials: square-free decomposition 526

20.4 Factoring polynomials: the Cantor–Zassenhaus algorithm 530

20.5 Factoring polynomials: Berlekamp’s algorithm 538

20.6 Deterministic factorization algorithms () 544

20.7 Notes 546

21 Deterministic primality testing 548

21.1 The basic idea 548

21.2 The algorithm and its analysis 549

21.3 Notes 558

Appendix: Some useful facts 561

Bibliography 566

Index of notation 572

Index 574

## Preface

Number theory and algebra play an increasingly significant role in computing

and communications, as evidenced by the striking applications of these subjects

to such fields as cryptography and coding theory. My goal in writing this book

was to provide an introduction to number theory and algebra, with an emphasis

on algorithms and applications, that would be accessible to a broad audience. In

particular, I wanted to write a book that would be appropriate for typical students in

computer science or mathematics who have some amount of general mathematical

experience, but without presuming too much specific mathematical knowledge.

Prerequisites. The mathematical prerequisites are minimal: no particular mathematical

concepts beyond what is taught in a typical undergraduate calculus

sequence are assumed.

The computer science prerequisites are also quite minimal: it is assumed that the

reader is proficient in programming, and has had some exposure to the analysis of

algorithms, essentially at the level of an undergraduate course on algorithms and

data structures.

Even though it is mathematically quite self contained, the text does presuppose

that the reader is comfortable with mathematical formalism and also has

some experience in reading and writing mathematical proofs. Readers may have

gained such experience in computer science courses such as algorithms, automata

or complexity theory, or some type of “discrete mathematics for computer science

students” course. They also may have gained such experience in undergraduate

mathematics courses, such as abstract or linear algebra. The material in these mathematics

courses may overlap with some of the material presented here; however,

even if the reader already has had some exposure to this material, it nevertheless

may be convenient to have all of the relevant topics easily accessible in one place;

moreover, the emphasis and perspective here will no doubt be dierent from that

in a traditional mathematical presentation of these subjects.

Structure of the text. All of the mathematics required beyond basic calculus

is developed “from scratch.” Moreover, the book generally alternates between

“theory” and “applications”: one or two chapters on a particular set of purely

mathematical concepts are followed by one or two chapters on algorithms and

applications; the mathematics provides the theoretical underpinnings for the applications,

while the applications both motivate and illustrate the mathematics. Of

course, this dichotomy between theory and applications is not perfectly maintained:

the chapters that focus mainly on applications include the development

of some of the mathematics that is specific to a particular application, and very

occasionally, some of the chapters that focus mainly on mathematics include a

discussion of related algorithmic ideas as well.

In developing the mathematics needed to discuss certain applications, I have

tried to strike a reasonable balance between, on the one hand, presenting the absolute

minimum required to understand and rigorously analyze the applications, and

on the other hand, presenting a full-blown development of the relevant mathematics.

In striking this balance, I wanted to be fairly economical and concise, while at

the same time, I wanted to develop enough of the theory so as to present a fairly

well-rounded account, giving the reader more of a feeling for the mathematical

“big picture.”

The mathematical material covered includes the basics of number theory

(including unique factorization, congruences, the distribution of primes, and

quadratic reciprocity) and of abstract algebra (including groups, rings, fields, and

vector spaces). It also includes an introduction to discrete probability theory—this

material is needed to properly treat the topics of probabilistic algorithms and cryptographic

applications. The treatment of all these topics is more or less standard,

except that the text only deals with commutative structures (i.e., abelian groups and

commutative rings with unity)—this is all that is really needed for the purposes of

this text, and the theory of these structures is much simpler and more transparent

than that of more general, non-commutative structures.

The choice of topics covered in this book was motivated primarily by their

applicability to computing and communications, especially to the specific areas

of cryptography and coding theory. Thus, the book may be useful for reference

or self-study by readers who want to learn about cryptography, or it could also be

used as a textbook in a graduate or upper-division undergraduate course on (computational)

number theory and algebra, perhaps geared towards computer science

students.

Since this is an introduction, and not an encyclopedic reference for specialists,

some topics simply could not be covered. One such, whose exclusion will undoubtedly

be lamented by some, is the theory of lattices, along with algorithms for and

applications of lattice basis reduction. Another omission is fast algorithms for

integer and polynomial arithmetic—although some of the basic ideas of this topic

are developed in the exercises, the main body of the text deals only with classical,

quadratic-time algorithms for integer and polynomial arithmetic. However, there

are more advanced texts that cover these topics perfectly well, and they should be

readily 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 interesting

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

Guidelines for 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, which form an integral part of the

book, 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.

Some exercises are underlined. These develop important (but usually simple)

facts, and should be viewed as an integral part of the book. It is highly

recommended that the reader work these exercises, or at the very least, read

and understand their statements.

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 fixes 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.

The second edition. In preparing this second edition, in addition to correcting

errors in the first edition, I have also made a number of other modifications (hopefully

without introducing too many new errors). Many passages have been rewritten

to improve the clarity of exposition, and many new exercises and examples

have been added. Especially in the earlier chapters, the presentation is a bit more

leisurely. Some material has been reorganized. Most notably, the chapter on probability

now follows the chapters on groups and rings—this allows a number of

examples and concepts in the probability chapter that depend on algebra to be

more fully developed. Also, a number of topics have been moved forward in the

text, so as to enliven the material with exciting applications as soon as possible;

for example, the RSA cryptosystem is now described right after Euclid’s algorithm

is presented, and some basic results concerning quadratic residues are introduced

right away, in the chapter on congruences. Finally, there are numerous changes

in notation and terminology; for example, the notion of a family of objects is

now used consistently throughout the book (e.g., a pairwise independent family

of random variables, a linearly independent family of vectors, a pairwise relatively

prime family of integers, etc.).