| |
| |
Preface | |
| |
| |
Preliminaries | |
| |
| |
| |
Basic properties of the integers | |
| |
| |
| |
Divisibility and primality | |
| |
| |
| |
Ideals and greatest common divisors | |
| |
| |
| |
Some consequences of unique factorization | |
| |
| |
| |
Congruences | |
| |
| |
| |
Equivalence relations | |
| |
| |
| |
Definitions and basic properties of congruences | |
| |
| |
| |
Solving linear congruences | |
| |
| |
| |
The Chinese remainder theorem | |
| |
| |
| |
Residue classes | |
| |
| |
| |
Euler's phi function | |
| |
| |
| |
Euler's theorem and Fermat's little theorem | |
| |
| |
| |
Quadratic residues | |
| |
| |
| |
Summations over divisors | |
| |
| |
| |
Computing with large integers | |
| |
| |
| |
Asymptotic notation | |
| |
| |
| |
Machine models and complexity theory | |
| |
| |
| |
Basic integer arithmetic | |
| |
| |
| |
Computing in Z<sub>n</sub> | |
| |
| |
| |
Faster integer arithmetic (*) | |
| |
| |
| |
Notes | |
| |
| |
| |
Euclid's algorithm | |
| |
| |
| |
The basic Euclidean algorithm | |
| |
| |
| |
The extended Euclidean algorithm | |
| |
| |
| |
Computing modular inverses and Chinese remaindering | |
| |
| |
| |
Speeding up algorithms via modular computation | |
| |
| |
| |
An effective version of Fermat's two squares theorem | |
| |
| |
| |
Rational reconstruction and applications | |
| |
| |
| |
The RSA cryptosystem | |
| |
| |
| |
Notes | |
| |
| |
| |
The distribution of primes | |
| |
| |
| |
Chebyshev's theorem on the density of primes | |
| |
| |
| |
Bertrand's postulate | |
| |
| |
| |
Mertens' theorem | |
| |
| |
| |
The sieve of Eratosthenes | |
| |
| |
| |
The prime number theorem ...and beyond | |
| |
| |
| |
Notes | |
| |
| |
| |
Abelian groups | |
| |
| |
| |
Definitions, basic properties, and examples | |
| |
| |
| |
Subgroups | |
| |
| |
| |
Cosets and quotient groups | |
| |
| |
| |
Group homomorphisms and isomorphisms | |
| |
| |
| |
Cyclic groups | |
| |
| |
| |
The structure of finite abelian groups (*) | |
| |
| |
| |
Rings | |
| |
| |
| |
Definitions, basic properties, and examples | |
| |
| |
| |
Polynomial rings | |
| |
| |
| |
Ideals and quotient rings | |
| |
| |
| |
Ring homomorphisms and isomorphisms | |
| |
| |
| |
The structure of Z<sup>*</sup><sub>n</sub> | |
| |
| |
| |
Finite and discrete probability distributions | |
| |
| |
| |
Basic definitions | |
| |
| |
| |
Conditional probability and independence | |
| |
| |
| |
Random variables | |
| |
| |
| |
Expectation and variance | |
| |
| |
| |
Some useful bounds | |
| |
| |
| |
Balls and bins | |
| |
| |
| |
Hash functions | |
| |
| |
| |
Statistical distance | |
| |
| |
| |
Measures of randomness and the leftover hash lemma (*) | |
| |
| |
| |
Discrete probability distributions | |
| |
| |
| |
Notes | |
| |
| |
| |
Probabilistic algorithms | |
| |
| |
| |
Basic definitions | |
| |
| |
| |
Generating a random number from a given interval | |
| |
| |
| |
The generate and test paradigm | |
| |
| |
| |
Generating a random prime | |
| |
| |
| |
Generating a random non-increasing sequence | |
| |
| |
| |
Generating a random factored number | |
| |
| |
| |
Some complexity theory | |
| |
| |
| |
Notes | |
| |
| |
| |
Probabilistic primality testing | |
| |
| |
| |
Trial division | |
| |
| |
| |
The Miller-Rabin test | |
| |
| |
| |
Generating random primes using the Miller-Rabin test | |
| |
| |
| |
Factoring and computing Euler's phi function | |
| |
| |
| |
Notes | |
| |
| |
| |
Finding generators and discrete logarithms in Z<sup>*</sup><sub>p</sub> | |
| |
| |
| |
Finding a generator for Z<sup>*</sup><sub>p</sub> | |
| |
| |
| |
Computing discrete logarithms in Z<sup>*</sup><sub>p</sub> | |
| |
| |
| |
The Diffie-Hellman key establishment protocol | |
| |
| |
| |
Notes | |
| |
| |
| |
Quadratic reciprocity and computing modular square roots | |
| |
| |
| |
The Legendre symbol | |
| |
| |
| |
The Jacobi symbol | |
| |
| |
| |
Computing the Jacobi symbol | |
| |
| |
| |
Testing quadratic residuosity | |
| |
| |
| |
Computing modular square roots | |
| |
| |
| |
The quadratic residuosity assumption | |
| |
| |
| |
Notes | |
| |
| |
| |
Modules and vector spaces | |
| |
| |
| |
Definitions, basic properties, and examples | |
| |
| |
| |
Submodules and quotient modules | |
| |
| |
| |
Module homomorphisms and isomorphisms | |
| |
| |
| |
Linear independence and bases | |
| |
| |
| |
Vector spaces and dimension | |
| |
| |
| |
Matrices | |
| |
| |
| |
Basic definitions and properties | |
| |
| |
| |
Matrices and linear maps | |
| |
| |
| |
The inverse of a matrix | |
| |
| |
| |
Gaussian elimination | |
| |
| |
| |
Applications of Gaussian elimination | |
| |
| |
| |
Notes | |
| |
| |
| |
Subexponential-time discrete logarithms and factoring | |
| |
| |
| |
Smooth numbers | |
| |
| |
| |
An algorithm for discrete logarithms | |
| |
| |
| |
An algorithm for factoring integers | |
| |
| |
| |
Practical improvements | |
| |
| |
| |
Notes | |
| |
| |
| |
More rings | |
| |
| |
| |
Algebras | |
| |
| |
| |
The field of fractions of an integral domain | |
| |
| |
| |
Unique factorization of polynomials | |
| |
| |
| |
Polynomial congruences | |
| |
| |
| |
Minimal polynomials | |
| |
| |
| |
General properties of extension fields | |
| |
| |
| |
Formal derivatives | |
| |
| |
| |
Formal power series and Laurent series | |
| |
| |
| |
Unique factorization domains (*) | |
| |
| |
| |
Notes | |
| |
| |
| |
Polynomial arithmetic and applications | |
| |
| |
| |
Basic arithmetic | |
| |
| |
| |
Computing minimal polynomials in F[x]/(f)(I) | |
| |
| |
| |
Euclid's algorithm | |
| |
| |
| |
Computing modular inverses and Chinese remaindering | |
| |
| |
| |
Rational function reconstruction and applications | |
| |
| |
| |
Faster polynomial arithmetic (*) | |
| |
| |
| |
Notes | |
| |
| |
| |
Linearly generated sequences and applications | |
| |
| |
| |
Basic definitions and properties | |
| |
| |
| |
Computing minimal polynomials: a special case | |
| |
| |
| |
Computing minimal polynomials: a more general case | |
| |
| |
| |
Solving sparse linear systems | |
| |
| |
| |
Computing minimal polynomials in F[X]/(f)(II) | |
| |
| |
| |
The algebra of linear transformations (*) | |
| |
| |
| |
Notes | |
| |
| |
| |
Finite fields | |
| |
| |
| |
Preliminaries | |
| |
| |
| |
The existence of finite fields | |
| |
| |
| |
The subfield structure and uniqueness of finite fields | |
| |
| |
| |
Conjugates, norms and traces | |
| |
| |
| |
Algorithms for finite fields | |
| |
| |
| |
Tests for and constructing inrreducible polynomials | |
| |
| |
| |
Computing minimal polynomials in F[X](f)(III) | |
| |
| |
| |
Factoring polynomials: square-free decomposition | |
| |
| |
| |
Factoring polynomials: the Cantor-Zassenhaus algorithm | |
| |
| |
| |
Factoring polynomials: Berlekamp's algorithm | |
| |
| |
| |
Deterministic factorization algorithms (*) | |
| |
| |
| |
Notes | |
| |
| |
| |
Deterministic primality testing | |
| |
| |
| |
The basic idea | |
| |
| |
| |
The algorithm and its analysis | |
| |
| |
| |
Notes | |
| |
| |
Appendix: Some useful facts | |
| |
| |
Bibliography | |
| |
| |
Index of notation | |
| |
| |
Index | |