A computational introduction to number theory and algebra

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 32
2.2 Definitions and basic properties of congruences......Page 33
2.3 Solving linear congruences......Page 36
2.4 The Chinese remainder theorem......Page 39
2.5 Residue classes......Page 41
2.6 Euler\'s phi function......Page 48
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 67
3.2 Machine models and complexity theory......Page 70
3.3 Basic integer arithmetic......Page 72
3.4 Computing in Z_n......Page 82
3.5 Faster integer arithmetic (*)......Page 86
3.6 Notes......Page 88
4.1 The basic Euclidean algorithm......Page 91
4.2 The extended Euclidean algorithm......Page 94
4.3 Computing modular inverses and Chinese remaindering......Page 98
4.4 Speeding up algorithms via modular computation......Page 100
4.5 An effective version of Fermat\'s two squares theorem......Page 103
4.6 Rational reconstruction and applications......Page 106
4.7 The RSA cryptosystem......Page 116
4.8 Notes......Page 119
5.1 Chebyshev\'s theorem on the density of primes......Page 121
5.2 Bertrand\'s postulate......Page 125
5.3 Mertens\' theorem......Page 127
5.4 The sieve of Eratosthenes......Page 132
5.5 The prime number theorem …and beyond......Page 133
5.6 Notes......Page 141
6.1 Definitions, basic properties, and examples......Page 143
6.2 Subgroups......Page 149
6.3 Cosets and quotient groups......Page 154
6.4 Group homomorphisms and isomorphisms......Page 159
6.5 Cyclic groups......Page 170
6.6 The structure of finite abelian groups (*)......Page 180
7.1 Definitions, basic properties, and examples......Page 183
7.2 Polynomial rings......Page 193
7.3 Ideals and quotient rings......Page 202
7.4 Ring homomorphisms and isomorphisms......Page 208
7.5 The structure of Z_n*......Page 220
8.1 Basic definitions......Page 224
8.2 Conditional probability and independence......Page 230
8.3 Random variables......Page 238
8.4 Expectation and variance......Page 251
8.5 Some useful bounds......Page 258
8.6 Balls and bins......Page 262
8.7 Hash functions......Page 269
8.8 Statistical distance......Page 277
8.9 Measures of randomness and the leftover hash lemma (*)......Page 282
8.10 Discrete probability distributions......Page 287
8.11 Notes......Page 292
9 Probabilistic algorithms......Page 293
9.1 Basic definitions......Page 294
9.2 Generating a random number from a given interval......Page 301
9.3 The generate and test paradigm......Page 303
9.4 Generating a random prime......Page 308
9.5 Generating a random non-increasing sequence......Page 311
9.6 Generating a random factored number......Page 314
9.7 Some complexity theory......Page 318
9.8 Notes......Page 320
10.1 Trial division......Page 322
10.2 The Miller--Rabin test......Page 323
10.3 Generating random primes using the Miller--Rabin test......Page 327
10.4 Factoring and computing Euler\'s phi function......Page 336
10.5 Notes......Page 340
11.1 Finding a generator for Z_p*......Page 343
11.2 Computing discrete logarithms in Z_p*......Page 345
11.3 The Diffie--Hellman key establishment protocol......Page 351
11.4 Notes......Page 356
12.1 The Legendre symbol......Page 358
12.2 The Jacobi symbol......Page 362
12.3 Computing the Jacobi symbol......Page 364
12.4 Testing quadratic residuosity......Page 365
12.5 Computing modular square roots......Page 366
12.6 The quadratic residuosity assumption......Page 372
12.7 Notes......Page 373
13.1 Definitions, basic properties, and examples......Page 375
13.2 Submodules and quotient modules......Page 377
13.3 Module homomorphisms and isomorphisms......Page 379
13.4 Linear independence and bases......Page 384
13.5 Vector spaces and dimension......Page 387
14.1 Basic definitions and properties......Page 394
14.2 Matrices and linear maps......Page 398
14.3 The inverse of a matrix......Page 403
14.4 Gaussian elimination......Page 405
14.5 Applications of Gaussian elimination......Page 409
14.6 Notes......Page 415
15.1 Smooth numbers......Page 416
15.2 An algorithm for discrete logarithms......Page 417
15.3 An algorithm for factoring integers......Page 424
15.4 Practical improvements......Page 431
15.5 Notes......Page 436
16.1 Algebras......Page 438
16.2 The field of fractions of an integral domain......Page 443
16.3 Unique factorization of polynomials......Page 446
16.4 Polynomial congruences......Page 451
16.5 Minimal polynomials......Page 454
16.6 General properties of extension fields......Page 456
16.7 Formal derivatives......Page 460
16.8 Formal power series and Laurent series......Page 462
16.9 Unique factorization domains (*)......Page 466
16.10 Notes......Page 480
17.1 Basic arithmetic......Page 481
17.2 Computing minimal polynomials in F[X]/(f) (I)......Page 484
17.3 Euclid\'s algorithm......Page 485
17.4 Computing modular inverses and Chinese remaindering......Page 488
17.5 Rational function reconstruction and applications......Page 490
17.6 Faster polynomial arithmetic (*)......Page 494
17.7 Notes......Page 500
18.1 Basic definitions and properties......Page 502
18.2 Computing minimal polynomials: a special case......Page 506
18.3 Computing minimal polynomials: a more general case......Page 508
18.4 Solving sparse linear systems......Page 513
18.5 Computing minimal polynomials in F[X]/(f) (II)......Page 516
18.6 The algebra of linear transformations (*)......Page 517
18.7 Notes......Page 524
19.1 Preliminaries......Page 525
19.2 The existence of finite fields......Page 527
19.3 The subfield structure and uniqueness of finite fields......Page 531
19.4 Conjugates, norms and traces......Page 533
20.1 Generating and constructing irreducible polynomials......Page 539
20.2 Computing minimal polynomials in F[X]/(f) (III)......Page 542
20.3 Factoring polynomials: square-free decomposition......Page 543
20.4 Factoring polynomials: the Cantor--Zassenhaus algorithm......Page 547
20.5 Factoring polynomials: Berlekamp\'s algorithm......Page 555
20.6 Deterministic factorization algorithms (*)......Page 561
20.7 Notes......Page 563
21.1 The basic idea......Page 565
21.2 The algorithm and its analysis......Page 566
21.3 Notes......Page 576
Appendix: Some useful facts......Page 577
Bibliography......Page 582
Index of notation......Page 588
Index......Page 590