Emociones

A Computational Introduction to Number Theory
and Algebra
(Version 2)
Victor Shoup

This PDF document contains hyperlinks, and one may navigate through it by clicking on theorem, definition, lemma, equation, and page numbers, as well as URLs,
and chapter and section titles in the table of contents; most PDF viewers should
also display a list of “bookmarks” that allow direct access tochapters and sections.

Copyright © 2008 by Victor Shoup
The electronic version of this work is distributed under the terms and conditions of
a Creative Commons license (Attribution-NonCommercial-NoDerivs 3.0):
You are free to copy, distribute, and display the electronic version
of this work under the following conditions:
Attribution. You must give the original author credit.
Noncommercial.You may not use the electronic version of this
work for commercial purposes.
No Derivative Works. You may not alter, transform, or build upon
the electronic version of this work.
For any reuse or distribution, you must make these license terms
clear to others.
Any of these conditions can be waived if you get permission from
the author.
For more information about the license, visitcreativecommons.org/licenses/by-nd-nc/3.0.
All other rights reserved. In particular, the right to publish or distribute this work
in print form belongs exclusively to Cambridge University Press.

Contents

page x
xiv

Preface
Preliminaries
1

Basic properties of the integers
1.1 Divisibility and primality
1.2 Ideals and greatest common divisors
1.3 Some consequences of uniquefactorization

1
1
5
10

2

Congruences
2.1 Equivalence relations
2.2 Definitions and basic properties of congruences
2.3 Solving linear congruences
2.4 The Chinese remainder theorem
2.5 Residue classes
2.6 Euler’s phi function
2.7 Euler’s theorem and Fermat’s little theorem
2.8 Quadratic residues
2.9 Summations over divisors

15
15
16
19
22
25
31
32
35
45

3

Computing withlarge integers
3.1 Asymptotic notation
3.2 Machine models and complexity theory
3.3 Basic integer arithmetic
3.4 Computing in Zn
3.5 Faster integer arithmetic (∗)
3.6 Notes

50
50
53
55
64
69
71

4

Euclid’s algorithm
4.1 The basic Euclidean algorithm
4.2 The extended Euclidean algorithm
4.3 Computing modular inverses and Chinese remaindering

74
74
77
82

v

viContents

4.4
4.5
4.6
4.7
4.8

Speeding up algorithms via modular computation
An effective version of Fermat’s two squares theorem
Rational reconstruction and applications
The RSA cryptosystem
Notes

84
86
89
99
102

5

The distribution of primes
5.1 Chebyshev’s theorem on the density of primes
5.2 Bertrand’s postulate
5.3 Mertens’ theorem
5.4 The sieve of Eratosthenes
5.5The prime number theorem . . . and beyond
5.6 Notes

104
104
108
110
115
116
124

6

Abelian groups
6.1 Definitions, basic properties, and examples
6.2 Subgroups
6.3 Cosets and quotient groups
6.4 Group homomorphisms and isomorphisms
6.5 Cyclic groups
6.6 The structure of finite abelian groups (∗)

126
126
132
137
142
153
163

7

Rings
7.1 Definitions, basicproperties, and examples
7.2 Polynomial rings
7.3 Ideals and quotient rings
7.4 Ring homomorphisms and isomorphisms
7.5 The structure of Z∗
n

166
166
176
185
192
203

8

Finite and discrete probability distributions
8.1 Basic definitions
8.2 Conditional probability and independence
8.3 Random variables
8.4 Expectation and variance
8.5 Some useful bounds
8.6 Balls and bins
8.7 Hashfunctions
8.8 Statistical distance
8.9 Measures of randomness and the leftover hash lemma (∗)
8.10 Discrete probability distributions
8.11 Notes

207
207
213
221
233
241
245
252
260
266
270
275

Contents

vii

9

Probabilistic algorithms
9.1 Basic definitions
9.2 Generating a random number from a given interval
9.3 The generate and test paradigm
9.4 Generating a random...