This introductory book emphasizes algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The presentation alternates between theory and applications in order to motivate and illustrate the mathematics. The mathematical coverage includes the basics of number theory, abstract algebra and discrete probability theory. This edition now includes over 150 new exercises, ranging from the routine to the challenging, that flesh out the material presented in the body of the text, and which further develop the theory and present new applications. The material has also been reorganized to improve clarity of exposition and presentation. Ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.
Author(s): Victor Shoup
Edition: 2
Publisher: Cambridge University Press
Year: 2009
Language: English
Pages: 598
Title......Page 1
Contents......Page 5
Preface......Page 10
Preliminaries......Page 14
1.1 Divisibility and primality......Page 19
1.2 Ideals and greatest common divisors......Page 23
1.3 Some consequences of unique factorization......Page 28
2.1 Equivalence relations......Page 33
2.2 Definitions and basic properties of congruences......Page 34
2.3 Solving linear congruences......Page 37
2.4 The Chinese remainder theorem......Page 40
2.5 Residue classes......Page 43
2.6 Euler's phi function......Page 49
2.7 Euler's theorem and Fermat's little theorem......Page 50
2.8 Quadratic residues......Page 53
2.9 Summations over divisors......Page 63
3.1 Asymptotic notation......Page 68
3.2 Machine models and complexity theory......Page 71
3.3 Basic integer arithmetic......Page 73
3.4 Computing in Zn......Page 82
3.5 Faster integer arithmetic (*)......Page 87
3.6 Notes......Page 89
4.1 The basic Euclidean algorithm......Page 92
4.2 The extended Euclidean algorithm......Page 95
4.3 Computing modular inverses and Chinese remaindering......Page 100
4.4 Speeding up algorithms via modular computation......Page 102
4.5 An effective version of Fermat's two squares theorem......Page 104
4.6 Rational reconstruction and applications......Page 107
4.7 The RSA cryptosystem......Page 117
4.8 Notes......Page 120
5.1 Chebyshev's theorem on the density of primes......Page 122
5.2 Bertrand's postulate......Page 126
5.3 Mertens' theorem......Page 128
5.4 The sieve of Eratosthenes......Page 133
5.5 The prime number theorem …and beyond......Page 134
5.6 Notes......Page 142
6.1 Definitions, basic properties, and examples......Page 144
6.2 Subgroups......Page 150
6.3 Cosets and quotient groups......Page 155
6.4 Group homomorphisms and isomorphisms......Page 160
6.5 Cyclic groups......Page 171
6.6 The structure of finite abelian groups (*)......Page 181
7.1 Definitions, basic properties, and examples......Page 184
7.2 Polynomial rings......Page 194
7.3 Ideals and quotient rings......Page 203
7.4 Ring homomorphisms and isomorphisms......Page 210
7.5 The structure of Zn*......Page 221
8.1 Basic definitions......Page 225
8.2 Conditional probability and independence......Page 231
8.3 Random variables......Page 239
8.4 Expectation and variance......Page 251
8.5 Some useful bounds......Page 259
8.6 Balls and bins......Page 263
8.7 Hash functions......Page 270
8.8 Statistical distance......Page 278
8.9 Measures of randomness and the leftover hash lemma (*)......Page 284
8.10 Discrete probability distributions......Page 288
8.11 Notes......Page 293
9 Probabilistic algorithms......Page 295
9.1 Basic definitions......Page 296
9.2 Generating a random number from a given interval......Page 303
9.3 The generate and test paradigm......Page 305
9.4 Generating a random prime......Page 310
9.5 Generating a random non-increasing sequence......Page 313
9.6 Generating a random factored number......Page 316
9.7 Some complexity theory......Page 320
9.8 Notes......Page 322
10.1 Trial division......Page 324
10.2 The Miller--Rabin test......Page 325
10.3 Generating random primes using the Miller--Rabin test......Page 329
10.4 Factoring and computing Euler's phi function......Page 338
10.5 Notes......Page 342
11.1 Finding a generator for Zp*......Page 345
11.2 Computing discrete logarithms in Zp*......Page 347
11.3 The Diffie--Hellman key establishment protocol......Page 352
11.4 Notes......Page 358
12.1 The Legendre symbol......Page 360
12.2 The Jacobi symbol......Page 364
12.3 Computing the Jacobi symbol......Page 366
12.4 Testing quadratic residuosity......Page 367
12.5 Computing modular square roots......Page 368
12.6 The quadratic residuosity assumption......Page 373
12.7 Notes......Page 375
13.1 Definitions, basic properties, and examples......Page 376
13.2 Submodules and quotient modules......Page 378
13.3 Module homomorphisms and isomorphisms......Page 381
13.4 Linear independence and bases......Page 385
13.5 Vector spaces and dimension......Page 388
14.1 Basic definitions and properties......Page 395
14.2 Matrices and linear maps......Page 399
14.3 The inverse of a matrix......Page 404
14.4 Gaussian elimination......Page 406
14.5 Applications of Gaussian elimination......Page 410
14.6 Notes......Page 416
15.1 Smooth numbers......Page 417
15.2 An algorithm for discrete logarithms......Page 418
15.3 An algorithm for factoring integers......Page 425
15.4 Practical improvements......Page 432
15.5 Notes......Page 436
16.1 Algebras......Page 439
16.2 The field of fractions of an integral domain......Page 445
16.3 Unique factorization of polynomials......Page 448
16.4 Polynomial congruences......Page 453
16.5 Minimal polynomials......Page 456
16.6 General properties of extension fields......Page 458
16.7 Formal derivatives......Page 462
16.8 Formal power series and Laurent series......Page 464
16.9 Unique factorization domains (*)......Page 469
16.10 Notes......Page 482
17.1 Basic arithmetic......Page 483
17.2 Computing minimal polynomials in F[X]/(f) (I)......Page 486
17.3 Euclid's algorithm......Page 487
17.4 Computing modular inverses and Chinese remaindering......Page 490
17.5 Rational function reconstruction and applications......Page 492
17.6 Faster polynomial arithmetic (*)......Page 496
17.7 Notes......Page 502
18.1 Basic definitions and properties......Page 504
18.2 Computing minimal polynomials: a special case......Page 508
18.3 Computing minimal polynomials: a more general case......Page 510
18.4 Solving sparse linear systems......Page 515
18.5 Computing minimal polynomials in F[X]/(f) (II)......Page 518
18.6 The algebra of linear transformations (*)......Page 519
18.7 Notes......Page 526
19.1 Preliminaries......Page 527
19.2 The existence of finite fields......Page 529
19.3 The subfield structure and uniqueness of finite fields......Page 533
19.4 Conjugates, norms and traces......Page 534
20.1 Tests for and constructing irreducible polynomials......Page 540
20.2 Computing minimal polynomials in F[X]/(f) (III)......Page 543
20.3 Factoring polynomials: square-free decomposition......Page 544
20.4 Factoring polynomials: the Cantor--Zassenhaus algorithm......Page 548
20.5 Factoring polynomials: Berlekamp's algorithm......Page 556
20.6 Deterministic factorization algorithms (*)......Page 562
20.7 Notes......Page 564
21.1 The basic idea......Page 566
21.2 The algorithm and its analysis......Page 567
21.3 Notes......Page 576
Appendix: Some useful facts......Page 579
Bibliography......Page 584
Index of notation......Page 590
Index......Page 592
