15.3 The inverse of a matrix 323

15.4 Gaussian elimination 324

15.5 Applications of Gaussian elimination 328

viii Contents

15.6 Notes 334

16 Subexponential-time discrete logarithms and factoring 336

16.1 Smooth numbers 336

16.2 An algorithm for discrete logarithms 337

16.3 An algorithm for factoring integers 344

16.4 Practical improvements 352

16.5 Notes 356

17 More rings 359

17.1 Algebras 359

17.2 The ¬eld of fractions of an integral domain 363

17.3 Unique factorization of polynomials 366

17.4 Polynomial congruences 371

17.5 Polynomial quotient algebras 374

17.6 General properties of extension ¬elds 376

17.7 Formal power series and Laurent series 378

17.8 Unique factorization domains (—) 383

17.9 Notes 397

18 Polynomial arithmetic and applications 398

18.1 Basic arithmetic 398

18.2 Computing minimal polynomials in F [X]/(f ) (I) 401

18.3 Euclid™s algorithm 402

18.4 Computing modular inverses and Chinese remaindering 405

18.5 Rational function reconstruction and applications 410

18.6 Faster polynomial arithmetic (—) 415

18.7 Notes 421

19 Linearly generated sequences and applications 423

19.1 Basic de¬nitions and properties 423

19.2 Computing minimal polynomials: a special case 428

19.3 Computing minimal polynomials: a more general case 429

19.4 Solving sparse linear systems 435

19.5 Computing minimal polynomials in F [X]/(f ) (II) 438

19.6 The algebra of linear transformations (—) 440

19.7 Notes 447

20 Finite ¬elds 448

20.1 Preliminaries 448

20.2 The existence of ¬nite ¬elds 450

20.3 The sub¬eld structure and uniqueness of ¬nite ¬elds 454

20.4 Conjugates, norms and traces 456

Contents ix

21 Algorithms for ¬nite ¬elds 462

21.1 Testing and constructing irreducible polynomials 462

21.2 Computing minimal polynomials in F [X]/(f ) (III) 465

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm 467

21.4 Factoring polynomials: Berlekamp™s algorithm 475

21.5 Deterministic factorization algorithms (—) 483

21.6 Faster square-free decomposition (—) 485

21.7 Notes 487

22 Deterministic primality testing 489

22.1 The basic idea 489

22.2 The algorithm and its analysis 490

22.3 Notes 500

Appendix: Some useful facts 501

Bibliography 504

Index of notation 510

Index 512

Preface

Number theory and algebra play an increasingly signi¬cant role in comput-

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

subjects to such ¬elds as cryptography and coding theory. My goal in writ-

ing 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

accessible to typical students in computer science or mathematics who have

a some amount of general mathematical experience, but without presuming

too much speci¬c 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 pro¬cient 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 pre-

suppose that the reader is comfortable with mathematical formalism and

has some experience in reading and writing mathematical proofs. Read-

ers may have gained such experience in computer science courses such as

algorithms, automata or complexity theory, or some type of “discrete math-

ematics for computer science students” course. They also may have gained

such experience in undergraduate mathematics courses, such as abstract or

linear algebra ” these courses overlap with some of the material presented

here, but even if the reader already has had some exposure to this material,

it nevertheless may be convenient to have all of the relevant material easily

accessible in one place, and moreover, the emphasis and perspective here

x

Preface xi

will no doubt be di¬erent than in a typical mathematics course on these

subjects.

Structure of the text. All of the mathematics required beyond basic cal-

culus 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 un-

derpinnings 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 speci¬c 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

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 abstract algebra (including groups, rings, ¬elds,

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 spe-

ci¬c areas of cryptography and coding theory. For example, the book may

be useful for reference or self-study by readers who want to learn about

cryptography. The book could also be used as a textbook in a graduate

xii Preface

or upper-division undergraduate course on (computational) number theory

and algebra, perhaps geared towards computer science students.

Since this is an introductory textbook, and not an encyclopedic reference

for specialists, some topics simply could not be covered. One such topic

whose exclusion will undoubtedly be lamented by some is the theory of

lattices, along with algorithms for and applications of lattice basis reduction.

Another such topic is that of 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. As an introductory

text, some topics just had to go; moreover, there are more advanced texts