A Computational Introduction to Number Theory and Algebra

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 11
Preface......Page 16
Sets and relations......Page 20
Functions......Page 21
Binary operations......Page 22
1.1 Divisibility and primality......Page 23
1.2 Ideals and greatest common divisors......Page 26
1.3 Some consequences of unique factorization......Page 30
2.1 Definitions and basic properties......Page 35
2.2 Solving linear congruences......Page 37
2.3 Residue classes......Page 42
2.4 Euler’s phi function......Page 46
2.5 Fermat’s little theorem......Page 47
2.6 Arithmetic functions and Möbius inversion......Page 50
3.1 Asymptotic notation......Page 55
3.2 Machine models and complexity theory......Page 58
3.3 Basic integer arithmetic......Page 61
3.3.2 Subtraction......Page 62
3.3.4 Division with remainder......Page 63
3.3.5 Summary......Page 68
3.4 Computing in Zn......Page 70
3.5 Faster integer arithmetic (*)......Page 73
3.6 Notes......Page 74
4.1 The basic Euclidean algorithm......Page 77
4.2 The extended Euclidean algorithm......Page 80
4.3 Computing modular inverses and Chinese remaindering......Page 84
4.4 Speeding up algorithms via modular computation......Page 85
4.5 Rational reconstruction and applications......Page 88
4.5.1 Application: Chinese remaindering with errors......Page 90
4.5.2 Application: recovering fractions from their decimal expansions......Page 91
4.5.3 Applications to symbolic algebra......Page 94
4.6 Notes......Page 95
5.1 Chebyshev’s theorem on the density of primes......Page 96
5.2 Bertrand’s postulate......Page 100
5.3 Mertens’ theorem......Page 103
5.4 The sieve of Eratosthenes......Page 107
5.5.1 The prime number theorem......Page 108
5.5.2 The error term in the prime number theorem......Page 109
5.5.4 Primes in arithmetic progressions......Page 113
5.5.5 Sophie Germain primes......Page 115
5.6 Notes......Page 116
6.1 Finite probability distributions: basic definitions......Page 118
6.2 Conditional probability and independence......Page 121
6.3 Random variables......Page 126
6.4 Expectation and variance......Page 133
6.5 Some useful bounds......Page 139
6.6 The birthday paradox......Page 143
6.7 Hash functions......Page 147
6.7.1 Hash tables......Page 148
6.7.2 Message authentication......Page 150
6.8 Statistical distance......Page 152
6.9 Measures of randomness and the leftover hash lemma (*)......Page 158
6.10.1 Basic definitions......Page 163
6.10.3 Random variables......Page 165
6.10.4 Expectation and variance......Page 166
6.10.5 Some useful bounds......Page 168
6.11 Notes......Page 169
7.1 Basic definitions......Page 170
7.1.1 Defining the probability distribution......Page 171
7.2.1 Reducing the error probability......Page 177
7.2.3 Language recognition......Page 178
7.3 Flipping a coin until a head appears......Page 180
7.4 Generating a random number from a given interval......Page 181
7.5 Generating a random prime......Page 184
7.5.1 Using a probabilistic primality test......Page 186
7.5.2 Generating a random k-bit prime......Page 188
7.6 Generating a random non-increasing sequence......Page 189
7.6.1 Analysis of the output distribution......Page 190
7.6.2 Analysis of the running time......Page 191
7.7 Generating a random factored number......Page 192
7.7.1 Using a probabilistic primality test (*)......Page 194
7.8 The RSA cryptosystem......Page 196
7.9 Notes......Page 201
8.1 Definitions, basic properties, and examples......Page 202
8.2 Subgroups......Page 207
8.3 Cosets and quotient groups......Page 212
8.4 Group homomorphisms and isomorphisms......Page 216
8.5 Cyclic groups......Page 224
8.6 The structure of flnite abelian groups (*)......Page 230
9.1 Definitions, basic properties, and examples......Page 233
9.1.1 Units and fields......Page 236
9.1.2 Zero divisors and integral domains......Page 237
9.1.3 Subrings......Page 240
9.2 Polynomial rings......Page 242
9.2.1 Polynomials versus polynomial functions......Page 244
9.2.2 Basic properties of polynomial rings......Page 245
9.2.3 Division with remainder......Page 246
9.2.4 Formal derivatives......Page 249
9.2.5 Multi-variate polynomials......Page 250
9.3 Ideals and quotient rings......Page 253
9.4 Ring homomorphisms and isomorphisms......Page 258
10.1 Trial division......Page 266
10.2 The structure of Zn......Page 267
10.3 The Miller–Rabin test......Page 269
10.4.1 Generating a random prime between 2 and M......Page 274
10.4.2 Trial division up to a small bound......Page 278
10.4.3 Generating a random k-bit prime......Page 282
10.5 Perfect power testing and prime power factoring......Page 283
10.6 Factoring and computing Euler’s phi function......Page 284
10.7 Notes......Page 288
11.1 Finding a generator for Z.p......Page 290
11.2.1 Brute-force search......Page 292
11.2.2 Baby step/giant step method......Page 293
11.2.3 Groups of order qe......Page 294
11.2.5 A space-efficient square-root time algorithm......Page 296
11.3 The Diffle–Hellman key establishment protocol......Page 297
11.4 Notes......Page 303
12.1 Quadratic residues......Page 305
12.2 The Legendre symbol......Page 307
12.3 The Jacobi symbol......Page 309
12.4 Notes......Page 311
13.1 Computing the Jacobi symbol......Page 312
13.2.3 Composite modulus......Page 313
13.3.1 Prime modulus......Page 314
13.3.2 Prime-power modulus......Page 316
13.3.3 Composite modulus......Page 317
13.4 The quadratic residuosity assumption......Page 319
13.5 Notes......Page 320
14.1 Definitions, basic properties, and examples......Page 321
14.2 Submodules and quotient modules......Page 323
14.3 Module homomorphisms and isomorphisms......Page 325
14.4 Linear independence and bases......Page 328
14.5 Vector spaces and dimension......Page 331
15.1 Basic definitions and properties......Page 338
15.2 Matrices and linear maps......Page 342
15.3 The inverse of a matrix......Page 345
15.4 Gaussian elimination......Page 346
15.5 Applications of Gaussian elimination......Page 350
Computing the image and kernel......Page 351
Solving linear systems of equations......Page 352
The orthogonal complement of a subspace......Page 353
15.6 Notes......Page 356
16.1 Smooth numbers......Page 358
16.2 An algorithm for discrete logarithms......Page 359
16.3 An algorithm for factoring integers......Page 366
16.4.1 Better smoothness density estimates......Page 374
16.4.2 The quadratic sieve algorithm......Page 375
16.5 Notes......Page 378
17.1 Algebras......Page 381
R-algebra homomorphisms......Page 382
Polynomial evaluation......Page 383
R-algebras as R-modules......Page 384
17.2 The field of fractions of an integral domain......Page 385
17.3 Unique factorization of polynomials......Page 388
17.4 Polynomial congruences......Page 393
17.5 Polynomial quotient algebras......Page 396
17.6 General properties of extension fields......Page 398
17.7 Formal power series and Laurent series......Page 400
17.7.1 Formal power series......Page 401
17.7.2 Formal Laurent series......Page 402
17.7.3 Reversed formal Laurent series......Page 403
17.8 Unique factorization domains (*)......Page 405
17.8.1 Unique factorization in Euclidean and principal ideal domains......Page 409
17.8.2 Unique factorization in D[X]......Page 414
17.9 Notes......Page 419
18.1 Basic arithmetic......Page 420
18.2 Computing minimal polynomials in F[X]/(f) (I)......Page 423
18.3 Euclid’s algorithm......Page 424
18.4 Computing modular inverses and Chinese remaindering......Page 427
18.4.1 Chinese remaindering and polynomial interpolation......Page 428
18.4.2 Mutual independence and secret sharing......Page 429
18.4.3 Speeding up algorithms via modular computation......Page 431
18.5 Rational function reconstruction and applications......Page 432
18.5.1 Application: polynomial interpolation with errors......Page 433
18.5.2 Application: recovering rational functions from their reversed formal Laurent series......Page 435
18.5.3 Applications to symbolic algebra......Page 436
18.6 Faster polynomial arithmetic (*)......Page 437
18.7 Notes......Page 443
19.1 Basic definitions and properties......Page 445
19.2 Computing minimal polynomials: a special case......Page 450
19.3 Computing minimal polynomials: a more general case......Page 451
19.4 Solving sparse linear systems......Page 457
19.5 Computing minimal polynomials in F[X]/(f) (II)......Page 460
19.6 The algebra of linear transformations (*)......Page 462
19.7 Notes......Page 469
20.1 Preliminaries......Page 470
20.2 The existence of finite fields......Page 472
20.3 The subfield structure and uniqueness of finite fields......Page 476
20.4 Conjugates, norms and traces......Page 478
21.1 Testing and constructing irreducible polynomials......Page 484
21.2 Computing minimal polynomials in F[X]/(f) (III)......Page 487
21.3.1 Distinct degree factorization......Page 489
21.3.2 Equal degree factorization......Page 491
21.3.3 Analysis of the whole algorithm......Page 496
21.4 Factoring polynomials: Berlekamp’s algorithm......Page 497
21.4.1 A simple square-free decomposition algorithm......Page 498
Stage 1: Construct a basis for B......Page 500
Stage 2: Splitting with B......Page 502
21.4.3 Analysis of the whole algorithm......Page 504
21.5 Deterministic factorization algorithms (*)......Page 505
21.6 Faster square-free decomposition (*)......Page 507
21.7 Notes......Page 509
22.1 The basic idea......Page 511
22.2 The algorithm and its analysis......Page 512
22.2.1 Running time analysis......Page 513
22.2.2 Correctness......Page 514
22.3 Notes......Page 522
Appendix: Some useful facts......Page 523
Bibliography......Page 526
Index of notation......Page 532
Index......Page 534