A computational introduction to number theory and algebra

Contents......Page 6
Preface......Page 11
Preliminaries......Page 15
1.1 Divisibility and primality......Page 18
1.2 Ideals and greatest common divisors......Page 21
1.3 Some consequences of unique factorization......Page 25
2.1 Definitions and basic properties......Page 30
2.2 Solving linear congruences......Page 32
2.3 Residue classes......Page 37
2.4 Euler's phi function......Page 41
2.5 Fermat's little theorem......Page 42
2.6 Arithmetic functions and Möbius inversion......Page 45
3.1 Asymptotic notation......Page 50
3.2 Machine models and complexity theory......Page 53
3.3 Basic integer arithmetic......Page 56
3.4 Computing in Zn......Page 65
3.5 Faster integer arithmetic (*)......Page 68
3.6 Notes......Page 69
4.1 The basic Euclidean algorithm......Page 72
4.2 The extended Euclidean algorithm......Page 75
4.3 Computing modular inverses and Chinese remaindering......Page 79
4.4 Speeding up algorithms via modular computation......Page 80
4.5 Rational reconstruction and applications......Page 83
4.6 Notes......Page 90
5.1 Chebyshev's theorem on the density of primes......Page 91
5.2 Bertrand's postulate......Page 95
5.3 Mertens' theorem......Page 98
5.4 The sieve of Eratosthenes......Page 102
5.5 The prime number theorem …and beyond......Page 103
5.6 Notes......Page 111
6.1 Finite probability distributions: basic definitions......Page 113
6.2 Conditional probability and independence......Page 116
6.3 Random variables......Page 121
6.4 Expectation and variance......Page 128
6.5 Some useful bounds......Page 134
6.6 The birthday paradox......Page 138
6.7 Hash functions......Page 142
6.8 Statistical distance......Page 147
6.9 Measures of randomness and the leftover hash lemma (*)......Page 153
6.10 Discrete probability distributions......Page 158
6.11 Notes......Page 164
7.1 Basic definitions......Page 165
7.2 Approximation of functions......Page 172
7.3 Flipping a coin until a head appears......Page 175
7.4 Generating a random number from a given interval......Page 176
7.5 Generating a random prime......Page 179
7.6 Generating a random non-increasing sequence......Page 184
7.7 Generating a random factored number......Page 187
7.8 The RSA cryptosystem......Page 191
7.9 Notes......Page 196
8.1 Definitions, basic properties, and examples......Page 197
8.2 Subgroups......Page 202
8.3 Cosets and quotient groups......Page 207
8.4 Group homomorphisms and isomorphisms......Page 211
8.5 Cyclic groups......Page 219
8.6 The structure of finite abelian groups (*)......Page 225
9.1 Definitions, basic properties, and examples......Page 228
9.2 Polynomial rings......Page 237
9.3 Ideals and quotient rings......Page 248
9.4 Ring homomorphisms and isomorphisms......Page 253
10.1 Trial division......Page 261
10.2 The structure of Zn*......Page 262
10.3 The Miller--Rabin test......Page 264
10.4 Generating random primes using the Miller--Rabin test......Page 269
10.5 Perfect power testing and prime power factoring......Page 278
10.6 Factoring and computing Euler's phi function......Page 279
10.7 Notes......Page 283
11.1 Finding a generator for Zp*......Page 285
11.2 Computing discrete logarithms Zp*......Page 287
11.3 The Diffie--Hellman key establishment protocol......Page 292
11.4 Notes......Page 298
12.1 Quadratic residues......Page 300
12.2 The Legendre symbol......Page 302
12.3 The Jacobi symbol......Page 304
12.4 Notes......Page 306
13.1 Computing the Jacobi symbol......Page 307
13.2 Testing quadratic residuosity......Page 308
13.3 Computing modular square roots......Page 309
13.4 The quadratic residuosity assumption......Page 314
13.5 Notes......Page 315
14.1 Definitions, basic properties, and examples......Page 316
14.2 Submodules and quotient modules......Page 318
14.3 Module homomorphisms and isomorphisms......Page 320
14.4 Linear independence and bases......Page 323
14.5 Vector spaces and dimension......Page 326
15.1 Basic definitions and properties......Page 333
15.2 Matrices and linear maps......Page 337
15.3 The inverse of a matrix......Page 340
15.4 Gaussian elimination......Page 341
15.5 Applications of Gaussian elimination......Page 345
15.6 Notes......Page 351
16.1 Smooth numbers......Page 353
16.2 An algorithm for discrete logarithms......Page 354
16.3 An algorithm for factoring integers......Page 361
16.4 Practical improvements......Page 369
16.5 Notes......Page 373
17.1 Algebras......Page 376
17.2 The field of fractions of an integral domain......Page 380
17.3 Unique factorization of polynomials......Page 383
17.4 Polynomial congruences......Page 388
17.5 Polynomial quotient algebras......Page 391
17.6 General properties of extension fields......Page 393
17.7 Formal power series and Laurent series......Page 395
17.8 Unique factorization domains (*)......Page 400
17.9 Notes......Page 414
18.1 Basic arithmetic......Page 415
18.2 Computing minimal polynomials in F[X]/(f) (I)......Page 418
18.3 Euclid's algorithm......Page 419
18.4 Computing modular inverses and Chinese remaindering......Page 422
18.5 Rational function reconstruction and applications......Page 427
18.6 Faster polynomial arithmetic (*)......Page 432
18.7 Notes......Page 438
19.1 Basic definitions and properties......Page 440
19.2 Computing minimal polynomials: a special case......Page 445
19.3 Computing minimal polynomials: a more general case......Page 446
19.4 Solving sparse linear systems......Page 452
19.5 Computing minimal polynomials in F[X]/(f) (II)......Page 455
19.6 The algebra of linear transformations (*)......Page 457
19.7 Notes......Page 464
20.1 Preliminaries......Page 465
20.2 The existence of finite fields......Page 467
20.3 The subfield structure and uniqueness of finite fields......Page 471
20.4 Conjugates, norms and traces......Page 473
21.1 Testing and constructing irreducible polynomials......Page 479
21.2 Computing minimal polynomials in F[X]/(f) (III)......Page 482
21.3 Factoring polynomials: the Cantor--Zassenhaus algorithm......Page 484
21.4 Factoring polynomials: Berlekamp's algorithm......Page 492
21.5 Deterministic factorization algorithms (*)......Page 500
21.6 Faster square-free decomposition (*)......Page 502
21.7 Notes......Page 504
22.1 The basic idea......Page 506
22.2 The algorithm and its analysis......Page 507
22.3 Notes......Page 517
Appendix: Some useful facts......Page 518
Bibliography......Page 521
Index of notation......Page 527
Index......Page 529