A computational introduction to number theory and algebra

Shoup V.

Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such fields as cryptography and coding theory. This introductory book emphasises algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The mathematical prerequisites are minimal: nothing beyond material in a typical undergraduate course in calculus is presumed, other than some experience in doing proofs – everything else is developed from scratch. Thus the book can serve several purposes. It can be used as a reference and for self-study by readers who want to learn the mathematical foundations of modern cryptography. It is also ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.

---

Table of contents :
Preface……Page 3
Preliminaries……Page 6
Contents……Page 8
Divisibility and Primality……Page 13
Ideals and Greatest Common Divisors……Page 15
More on Unique Factorization and Greatest Common Divisors……Page 18
Definitions and Basic Properties……Page 21
Solving Linear Congruences……Page 22
Residue Classes……Page 25
Euler’s Phi-Function……Page 27
Fermat’s Little Theorem……Page 29
Other Arithmetic Functions……Page 31
Asymptotic Notation……Page 35
Machine Models and Complexity Theory……Page 37
Basic Integer Arithmetic……Page 40
Computing in Zn……Page 47
Faster Integer Arithmetic……Page 49
Notes……Page 50
The Basic Euclidean Algorithm……Page 52
The Extended Euclidean Algorithm……Page 54
Computing Modular Inverses and Chinese Remaindering……Page 58
Speeding up Algorithms via Modular Computation……Page 59
Rational Reconstruction and Applications……Page 62
Notes……Page 69
Chebyshev’s Theorem on the Density of Primes……Page 70
Bertrand’s Postulate……Page 74
Mertens’ Theorem……Page 77
The Sieve of Eratosthenes……Page 81
The Prime Number Theorem …and Beyond……Page 82
Notes……Page 90
Finite Probability Distributions: Basic Definitions……Page 92
Conditional Probability and Independence……Page 95
Random Variables……Page 98
Expectation and Variance……Page 102
Some Useful Bounds……Page 105
The Birthday Paradox……Page 108
Statistical Distance……Page 112
Measures of Randomness and the Leftover Hash Lemma……Page 116
Discrete Probability Distributions……Page 121
Notes……Page 126
Basic Definitions……Page 127
Approximation of Functions……Page 133
Flipping a Coin until a Head Appears……Page 134
Generating a Random Number from a Given Interval……Page 135
Generating a Random Prime……Page 137
Generating a Random Non-Increasing Sequence……Page 141
Generating a Random Factored Number……Page 145
Notes……Page 148
Definitions, Basic Properties, and Some Examples……Page 149
Subgroups……Page 153
Cosets and Quotient Groups……Page 158
Group Homomorphisms and Isomorphisms……Page 161
Cyclic Groups……Page 167
The Structure of Finite Abelian Groups……Page 173
Definitions, Basic Properties, and Examples……Page 176
Polynomial rings……Page 183
Ideals and Quotient Rings……Page 188
Ring Homomorphisms and Isomorphisms……Page 191
Trial Division……Page 198
The Structure of Zn*……Page 199
The Miller-Rabin Test……Page 201
Generating Random Primes using the Miller-Rabin Test……Page 207
Perfect Power Testing and Prime Power Factoring……Page 216
Factoring and Computing Euler’s Phi-Function……Page 217
The RSA Cryptosystem……Page 221
Notes……Page 223
Finding a Generator for Zp*……Page 225
Computing Discrete Logarithms Zp*……Page 227
The Diffie-Hellman Key Establishment Protocol……Page 232
Notes……Page 235
Quadratic Residues……Page 236
The Legendre Symbol……Page 238
The Jacobi Symbol……Page 240
Notes……Page 242
Computing the Jacobi Symbol……Page 243
Computing Modular Square Roots……Page 244
The Quadratic Residuosity Assumption……Page 248
Definitions, Properties, and Some Examples……Page 250
Submodules and Quotient Modules……Page 252
Module Homomorphisms and Isomorphisms……Page 253
Linear Independence and Bases……Page 255
Dimension……Page 257
Basic Definitions and Properties……Page 261
Matrices and Linear Maps……Page 265
The Inverse of a Matrix……Page 267
Gaussian Elimination……Page 268
Applications of Gaussian Elimination……Page 271
Notes……Page 276
Smooth Numbers……Page 277
An Algorithm for Discrete Logarithms……Page 279
An Algorithm for Factoring Integers……Page 285
Practical Improvements……Page 292
Notes……Page 297
Algebras……Page 300
The Field of Fractions of an Integral Domain……Page 304
Unique Factorization of Polynomials……Page 305
Polynomial Congruences……Page 309
Polynomial Quotient Algebras……Page 312
General Properties of Extension Fields……Page 314
Formal Derivatives……Page 316
Formal Power Series and Laurent Series……Page 318
Unique Factorization Domains……Page 322
Constructing the Real Numbers……Page 333
Basic Arithmetic……Page 336
Faster Polynomial Arithmetic……Page 338
Euclid’s Algorithm……Page 339
Computing Modular Inverses and Chinese Remaindering……Page 342
Rational Function Reconstruction and Applications……Page 347
Notes……Page 352
Basic Definitions and Properties……Page 354
Computing Minimal Polynomials — a Special Case……Page 357
Computing Minimal Polynomials — a More General Case……Page 358
Solving Sparse Linear Systems……Page 364
Computing Minimal Polynomials in F[X]/(f) (II)……Page 367
The Algebra of Linear Transformations……Page 369
Notes……Page 373
The Characteristic and Cardinality of a Finite Field……Page 374
Some Useful Divisibility Criteria……Page 375
The Existence of Finite Fields……Page 376
The Subfield Structure and Uniqueness of Finite Fields……Page 380
Conjugates, Norms and Traces……Page 381
Testing and Constructing Irreducible Polynomials……Page 388
Computing Minimal Polynomials in F[X]/(f) (III)……Page 392
Factoring Polynomials: The Cantor-Zassenhaus Algorithm……Page 393
Factoring Polynomials: Berlekamp’s Algorithm……Page 400
Deterministic Factorization Algorithms……Page 407
Faster Square-Free Decomposition……Page 409
Notes……Page 411
The Basic Idea……Page 413
The Algorithm and its Analysis……Page 414
Notes……Page 424
Some Useful Facts……Page 426
Bibliography……Page 429