A Computational Introduction to Number Theory and Algebra

Victor Shoup9780521851541, 0521851548

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. This introductory book emphasises algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The mathematical prerequisites are minimal: nothing beyond material in a typical undergraduate course in calculus is presumed, other than some experience in doing proofs – everything else is developed from scratch. Thus the book can serve several purposes. It can be used as a reference and for self-study by readers who want to learn the mathematical foundations of modern cryptography. It is also ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.

---

Table of contents :
Contents……Page 5
Preface……Page 10
Preliminaries……Page 14
1.1 Divisibility and primality……Page 17
1.2 Ideals and greatest common divisors……Page 20
1.3 Some consequences of unique factorization……Page 24
2.1 Definitions and basic properties……Page 29
2.2 Solving linear congruences……Page 31
2.3 Residue classes……Page 36
2.4 Euler’s phi function……Page 40
2.5 Fermat’s little theorem……Page 41
2.6 Arithmetic functions and Möbius inversion……Page 44
3.1 Asymptotic notation……Page 49
3.2 Machine models and complexity theory……Page 52
3.3 Basic integer arithmetic……Page 55
3.4 Computing in Zn……Page 64
3.5 Faster integer arithmetic (*)……Page 67
3.6 Notes……Page 68
4.1 The basic Euclidean algorithm……Page 71
4.2 The extended Euclidean algorithm……Page 74
4.3 Computing modular inverses and Chinese remaindering……Page 78
4.4 Speeding up algorithms via modular computation……Page 79
4.5 Rational reconstruction and applications……Page 82
4.6 Notes……Page 89
5.1 Chebyshev’s theorem on the density of primes……Page 90
5.2 Bertrand’s postulate……Page 94
5.3 Mertens’ theorem……Page 97
5.4 The sieve of Eratosthenes……Page 101
5.5 The prime number theorem …and beyond……Page 102
5.6 Notes……Page 110
6.1 Finite probability distributions: basic definitions……Page 112
6.2 Conditional probability and independence……Page 115
6.3 Random variables……Page 120
6.4 Expectation and variance……Page 127
6.5 Some useful bounds……Page 133
6.6 The birthday paradox……Page 137
6.7 Hash functions……Page 141
6.8 Statistical distance……Page 146
6.9 Measures of randomness and the leftover hash lemma (*)……Page 152
6.10 Discrete probability distributions……Page 157
6.11 Notes……Page 163
7.1 Basic definitions……Page 164
7.2 Approximation of functions……Page 171
7.3 Flipping a coin until a head appears……Page 174
7.4 Generating a random number from a given interval……Page 175
7.5 Generating a random prime……Page 178
7.6 Generating a random non-increasing sequence……Page 183
7.7 Generating a random factored number……Page 186
7.8 The RSA cryptosystem……Page 190
7.9 Notes……Page 195
8.1 Definitions, basic properties, and examples……Page 196
8.2 Subgroups……Page 201
8.3 Cosets and quotient groups……Page 206
8.4 Group homomorphisms and isomorphisms……Page 210
8.5 Cyclic groups……Page 218
8.6 The structure of finite abelian groups (*)……Page 224
9.1 Definitions, basic properties, and examples……Page 227
9.2 Polynomial rings……Page 236
9.3 Ideals and quotient rings……Page 247
9.4 Ring homomorphisms and isomorphisms……Page 252
10.1 Trial division……Page 260
10.2 The structure of Zn*……Page 261
10.3 The Miller–Rabin test……Page 263
10.4 Generating random primes using the Miller–Rabin test……Page 268
10.5 Perfect power testing and prime power factoring……Page 277
10.6 Factoring and computing Euler’s phi function……Page 278
10.7 Notes……Page 282
11.1 Finding a generator for Zp*……Page 284
11.2 Computing discrete logarithms Zp*……Page 286
11.3 The Diffie–Hellman key establishment protocol……Page 291
11.4 Notes……Page 297
12.1 Quadratic residues……Page 299
12.2 The Legendre symbol……Page 301
12.3 The Jacobi symbol……Page 303
12.4 Notes……Page 305
13.1 Computing the Jacobi symbol……Page 306
13.2 Testing quadratic residuosity……Page 307
13.3 Computing modular square roots……Page 308
13.4 The quadratic residuosity assumption……Page 313
13.5 Notes……Page 314
14.1 Definitions, basic properties, and examples……Page 315
14.2 Submodules and quotient modules……Page 317
14.3 Module homomorphisms and isomorphisms……Page 319
14.4 Linear independence and bases……Page 322
14.5 Vector spaces and dimension……Page 325
15.1 Basic definitions and properties……Page 332
15.2 Matrices and linear maps……Page 336
15.3 The inverse of a matrix……Page 339
15.4 Gaussian elimination……Page 340
15.5 Applications of Gaussian elimination……Page 344
15.6 Notes……Page 350
16.1 Smooth numbers……Page 352
16.2 An algorithm for discrete logarithms……Page 353
16.3 An algorithm for factoring integers……Page 360
16.4 Practical improvements……Page 368
16.5 Notes……Page 372
17.1 Algebras……Page 375
17.2 The field of fractions of an integral domain……Page 379
17.3 Unique factorization of polynomials……Page 382
17.4 Polynomial congruences……Page 387
17.5 Polynomial quotient algebras……Page 390
17.6 General properties of extension fields……Page 392
17.7 Formal power series and Laurent series……Page 394
17.8 Unique factorization domains (*)……Page 399
17.9 Notes……Page 413
18.1 Basic arithmetic……Page 414
18.2 Computing minimal polynomials in F[X]/(f) (I)……Page 417
18.3 Euclid’s algorithm……Page 418
18.4 Computing modular inverses and Chinese remaindering……Page 421
18.5 Rational function reconstruction and applications……Page 426
18.6 Faster polynomial arithmetic (*)……Page 431
18.7 Notes……Page 437
19.1 Basic definitions and properties……Page 439
19.2 Computing minimal polynomials: a special case……Page 444
19.3 Computing minimal polynomials: a more general case……Page 445
19.4 Solving sparse linear systems……Page 451
19.5 Computing minimal polynomials in F[X]/(f) (II)……Page 454
19.6 The algebra of linear transformations (*)……Page 456
19.7 Notes……Page 463
20.1 Preliminaries……Page 464
20.2 The existence of finite fields……Page 466
20.3 The subfield structure and uniqueness of finite fields……Page 470
20.4 Conjugates, norms and traces……Page 472
21.1 Testing and constructing irreducible polynomials……Page 478
21.2 Computing minimal polynomials in F[X]/(f) (III)……Page 481
21.3 Factoring polynomials: the Cantor–Zassenhaus algorithm……Page 483
21.4 Factoring polynomials: Berlekamp’s algorithm……Page 491
21.5 Deterministic factorization algorithms (*)……Page 499
21.6 Faster square-free decomposition (*)……Page 501
21.7 Notes……Page 503
22.1 The basic idea……Page 505
22.2 The algorithm and its analysis……Page 506
22.3 Notes……Page 516
Appendix: Some useful facts……Page 517
Bibliography……Page 520
Index of notation……Page 526
Index……Page 528