and Algebra

(Version 1)

Victor Shoup

This PDF document contains hyperlinks, and one may navigate through it

by clicking on theorem, de¬nition, 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 to chapters and sections.

Copyright c 2005 by Victor Shoup <victor@shoup.net>

All rights reserved. The right to publish or distribute this work in print form

belongs exclusively to Cambridge University Press; however, this electronic

version is distributed under the terms and conditions of a Creative Commons

license (Attribution-NonCommercial-NoDerivs 2.0):

You are free to copy, distribute, and display this electronic

version under the following conditions:

Attribution. You must give the original author credit.

Noncommercial. You may not use this electronic version for

commercial purposes.

No Derivative Works. You may not alter, transform, or

build upon this electronic version.

For any reuse or distribution, you must make clear to others

the license terms of this work.

Any of these conditions can be waived if you get permission

from the author.

For more information about the license, visit

creativecommons.org/licenses/by-nd-nc/2.0.

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 4

1.3 Some consequences of unique factorization 8

2 Congruences 13

2.1 De¬nitions and basic properties 13

2.2 Solving linear congruences 15

2.3 Residue classes 20

2.4 Euler™s phi function 24

2.5 Fermat™s little theorem 25

2.6 Arithmetic functions and M¨bius inversion

o 28

3 Computing with large integers 33

3.1 Asymptotic notation 33

3.2 Machine models and complexity theory 36

3.3 Basic integer arithmetic 39

3.4 Computing in Zn 48

3.5 Faster integer arithmetic (—) 51

3.6 Notes 52

4 Euclid™s algorithm 55

4.1 The basic Euclidean algorithm 55

4.2 The extended Euclidean algorithm 58

4.3 Computing modular inverses and Chinese remaindering 62

4.4 Speeding up algorithms via modular computation 63

4.5 Rational reconstruction and applications 66

4.6 Notes 73

v

vi Contents

5 The distribution of primes 74

5.1 Chebyshev™s theorem on the density of primes 74

5.2 Bertrand™s postulate 78

5.3 Mertens™ theorem 81

5.4 The sieve of Eratosthenes 85

5.5 The prime number theorem . . . and beyond 86

5.6 Notes 94

6 Finite and discrete probability distributions 96

6.1 Finite probability distributions: basic de¬nitions 96

6.2 Conditional probability and independence 99

6.3 Random variables 104

6.4 Expectation and variance 111

6.5 Some useful bounds 117

6.6 The birthday paradox 121

6.7 Hash functions 125

6.8 Statistical distance 130

6.9 Measures of randomness and the leftover hash lemma (—) 136

6.10 Discrete probability distributions 141

6.11 Notes 147

7 Probabilistic algorithms 148

7.1 Basic de¬nitions 148

7.2 Approximation of functions 155

7.3 Flipping a coin until a head appears 158

7.4 Generating a random number from a given interval 159

7.5 Generating a random prime 162

7.6 Generating a random non-increasing sequence 167

7.7 Generating a random factored number 170

7.8 The RSA cryptosystem 174

7.9 Notes 179

8 Abelian groups 180

8.1 De¬nitions, basic properties, and examples 180

8.2 Subgroups 185

8.3 Cosets and quotient groups 190

8.4 Group homomorphisms and isomorphisms 194

8.5 Cyclic groups 202

8.6 The structure of ¬nite abelian groups (—) 208

9 Rings 211

9.1 De¬nitions, basic properties, and examples 211

9.2 Polynomial rings 220

Contents vii

9.3 Ideals and quotient rings 231

9.4 Ring homomorphisms and isomorphisms 236

10 Probabilistic primality testing 244

10.1 Trial division 244

10.2 The structure of Z— 245

n

10.3 The Miller“Rabin test 247

10.4 Generating random primes using the Miller“Rabin test 252

10.5 Perfect power testing and prime power factoring 261

10.6 Factoring and computing Euler™s phi function 262

10.7 Notes 266

Finding generators and discrete logarithms in Z—

11 268

p

—

11.1 Finding a generator for Zp 268

11.2 Computing discrete logarithms Z— 270

p

11.3 The Di¬e“Hellman key establishment protocol 275

11.4 Notes 281

12 Quadratic residues and quadratic reciprocity 283

12.1 Quadratic residues 283

12.2 The Legendre symbol 285

12.3 The Jacobi symbol 287

12.4 Notes 289

13 Computational problems related to quadratic residues 290

13.1 Computing the Jacobi symbol 290

13.2 Testing quadratic residuosity 291

13.3 Computing modular square roots 292

13.4 The quadratic residuosity assumption 297

13.5 Notes 298

14 Modules and vector spaces 299

14.1 De¬nitions, basic properties, and examples 299

14.2 Submodules and quotient modules 301

14.3 Module homomorphisms and isomorphisms 303

14.4 Linear independence and bases 306

14.5 Vector spaces and dimension 309

15 Matrices 316

15.1 Basic de¬nitions and properties 316