| |

| |

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 | |