A Computational Introduction to Number Theory and Algebra

Описание

Preface xi
will no doubt be different than in a typical mathematics course on 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
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, 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. 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

Детали