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