A Computational Introduction To Number Theory and Algebra

Preface......Page 3
Contents......Page 7
0 Preliminaries......Page 13
1.1 Divisibility and Primality......Page 16
1.2 Ideals and Greatest Common Divisors......Page 19
1.3 Some Consequences of Unique Factorization......Page 22
2.1 Definitions and Basic Properties......Page 27
2.2 Solving Linear Congruences......Page 29
2.3 Residue Classes......Page 34
2.4 Euler's Phi Function......Page 38
2.5 Fermat's Little Theorem......Page 39
2.6 Arithmetic Functions and Möbius Inversion......Page 41
3.1 Asymptotic Notation......Page 46
3.2 Machine Models and Complexity Theory......Page 49
3.3 Basic Integer Arithmetic......Page 52
3.4 Computing in Zn......Page 60
3.5 Faster Integer Arithmetic......Page 63
3.6 Notes......Page 65
4.1 The Basic Euclidean Algorithm......Page 67
4.2 The Extended Euclidean Algorithm......Page 70
4.3 Computing Modular Inverses and Chinese Remaindering......Page 74
4.4 Speeding up Algorithms via Modular Computation......Page 75
4.5 Rational Reconstruction and Applications......Page 78
4.6 Notes......Page 84
5.1 Chebyshev's Theorem on the Density of Primes......Page 86
5.2 Bertrand's Postulate......Page 90
5.3 Mertens' Theorem......Page 93
5.4 The Sieve of Eratosthenes......Page 97
5.5 The Prime Number Theorem …and Beyond......Page 98
5.6 Notes......Page 106
6.1 Finite Probability Distributions: Basic Definitions......Page 108
6.2 Conditional Probability and Independence......Page 111
6.3 Random Variables......Page 116
6.4 Expectation and Variance......Page 122
6.5 Some Useful Bounds......Page 128
6.6 The Birthday Paradox......Page 132
6.7 Hash Functions......Page 136
6.8 Statistical Distance......Page 141
6.9 Measures of Randomness and the Leftover Hash Lemma......Page 145
6.10 Discrete Probability Distributions......Page 150
6.11 Notes......Page 155
7.1 Basic Definitions......Page 156
7.2 Approximation of Functions......Page 163
7.3 Flipping a Coin until a Head Appears......Page 165
7.4 Generating a Random Number from a Given Interval......Page 167
7.5 Generating a Random Prime......Page 169
7.6 Generating a Random Non-Increasing Sequence......Page 174
7.7 Generating a Random Factored Number......Page 177
7.8 The RSA Cryptosystem......Page 181
7.9 Notes......Page 185
8.1 Definitions, Basic Properties, and Examples......Page 187
8.2 Subgroups......Page 192
8.3 Cosets and Quotient Groups......Page 197
8.4 Group Homomorphisms and Isomorphisms......Page 200
8.5 Cyclic Groups......Page 209
8.6 The Structure of Finite Abelian Groups......Page 215
9.1 Definitions, Basic Properties, and Examples......Page 218
9.2 Polynomial rings......Page 226
9.3 Ideals and Quotient Rings......Page 236
9.4 Ring Homomorphisms and Isomorphisms......Page 241
10.1 Trial Division......Page 250
10.2 The Structure of Zn*......Page 251
10.3 The Miller-Rabin Test......Page 253
10.4 Generating Random Primes using the Miller-Rabin Test......Page 258
10.5 Perfect Power Testing and Prime Power Factoring......Page 267
10.6 Factoring and Computing Euler's Phi Function......Page 268
10.7 Notes......Page 272
11.1 Finding a Generator for Zp*......Page 274
11.2 Computing Discrete Logarithms Zp*......Page 276
11.3 The Diffie-Hellman Key Establishment Protocol......Page 281
11.4 Notes......Page 287
12.1 Quadratic Residues......Page 289
12.2 The Legendre Symbol......Page 290
12.3 The Jacobi Symbol......Page 293
12.4 Notes......Page 295
13.1 Computing the Jacobi Symbol......Page 296
13.2 Testing Quadratic Residuosity......Page 297
13.3 Computing Modular Square Roots......Page 298
13.4 The Quadratic Residuosity Assumption......Page 302
13.5 Notes......Page 303
14.1 Definitions, Basic Properties, and Examples......Page 305
14.2 Submodules and Quotient Modules......Page 307
14.3 Module Homomorphisms and Isomorphisms......Page 309
14.4 Linear Independence and Bases......Page 311
14.5 Vector Spaces and Dimension......Page 314
15.1 Basic Definitions and Properties......Page 320
15.2 Matrices and Linear Maps......Page 324
15.3 The Inverse of a Matrix......Page 326
15.4 Gaussian Elimination......Page 328
15.5 Applications of Gaussian Elimination......Page 331
15.6 Notes......Page 336
16.1 Smooth Numbers......Page 337
16.2 An Algorithm for Discrete Logarithms......Page 338
16.3 An Algorithm for Factoring Integers......Page 345
16.4 Practical Improvements......Page 352
16.5 Notes......Page 356
17.1 Algebras......Page 359
17.2 The Field of Fractions of an Integral Domain......Page 363
17.3 Unique Factorization of Polynomials......Page 366
17.4 Polynomial Congruences......Page 370
17.5 Polynomial Quotient Algebras......Page 373
17.6 General Properties of Extension Fields......Page 375
17.7 Formal Power Series and Laurent Series......Page 377
17.8 Unique Factorization Domains......Page 382
17.9 Notes......Page 395
18.1 Basic Arithmetic......Page 396
18.2 Computing Minimal Polynomials in F[X]/(f) (I)......Page 399
18.3 Euclid's Algorithm......Page 400
18.4 Computing Modular Inverses and Chinese Remaindering......Page 403
18.5 Rational Function Reconstruction and Applications......Page 408
18.6 Faster Polynomial Arithmetic......Page 412
18.7 Notes......Page 416
19.1 Basic Definitions and Properties......Page 418
19.2 Computing Minimal Polynomials --- a Special Case......Page 422
19.3 Computing Minimal Polynomials --- a More General Case......Page 424
19.4 Solving Sparse Linear Systems......Page 429
19.5 Computing Minimal Polynomials in F[X]/(f) (II)......Page 433
19.6 The Algebra of Linear Transformations......Page 434
19.7 Notes......Page 441
20.1 Preliminaries......Page 442
20.2 The Existence of Finite Fields......Page 444
20.3 The Subfield Structure and Uniqueness of Finite Fields......Page 448
20.4 Conjugates, Norms and Traces......Page 449
21.1 Testing and Constructing Irreducible Polynomials......Page 456
21.2 Computing Minimal Polynomials in F[X]/(f) (III)......Page 460
21.3 Factoring Polynomials: The Cantor-Zassenhaus Algorithm......Page 461
21.4 Factoring Polynomials: Berlekamp's Algorithm......Page 469
21.5 Deterministic Factorization Algorithms......Page 477
21.6 Faster Square-Free Decomposition......Page 479
21.7 Notes......Page 481
22.1 The Basic Idea......Page 483
22.2 The Algorithm and its Analysis......Page 484
22.3 Notes......Page 494
A Some Useful Facts......Page 496
Bibliography......Page 499
Index of Notation......Page 507
Index......Page 510