1 Euclid's Algorithm. - 1. 1 Euclidean Algorithm. - 1. 2 Diophantine Approximations. - 1. 3 Continued Fractions. - 1. 4 Diophantine Equations. - 2 Continued Fractions. - 2. 1 Basics. - 2. 2 Matrix Representation. - 2. 3 Continuant Representation. - 2. 4 Continued Fractions of Quadratics. - 2. 5 Approximation Properties. - 2. 6 Continued Fraction Arithmetic. - 3 Diophantine Equations. - 3. 1 Two Variable Linear Diophantine Equations. - 3. 2 General Linear Diophantine Equations. - 3. 3 Pell's Equation. - 3. 4 Fermat's Last Theorem. - 4 Lattice Techniques. - 4. 1 Lattice Fundamentals. - 4. 2 Minkowski Convex Body Theorem. - 4. 3 Reduced Bases. - 4. 4 Finding Numerical Relationships. - 5 Arithmetic Functions. - 5. 1 Arithmetic Functions. - 5. 2 Asymptotic Behavior of Arithmetic Functions. - 5. 3 Distribution of Primes. - 5. 4 Bertrand's Postulate. - 6 Residue Rings. - 6. 1 Basic Properties of ?/m?. - 6. 2 Chinese Remainder Theorem. - 6. 3 Multiplicative Structure of ?/m?. - 6. 4 Quadratic Reciprocity. - 6. 5 Algebraic Extensions of. - 6. 6 p-adic Numbers. - 6. 7 Cryptosystems. - 6. 8 Sums of Squares. - 7 Polynomial Arithmetic. - 7. 1 Generalities. - 7. 2 Polynomial Addition. - 7. 3 Polynomial Multiplication. - 7. 4 Fast Polynomial Algorithms. - 7. 5 Polynomial Exponentiation. - 7. 6 Polynomial Substitution. - 8 Polynomial GCD's: Classical Algorithms. - 8. 1 Generalities. - 8. 2 GCD of Several Quantities. - 8. 3 Polynomial Contents. - 8. 4 Coefficient Growth. - 8. 5 Pseudo-Quotients. - 8. 6 Subresultant Polynomial Remainder Sequence. - 9 Polynomial Elimination. - 9. 1 Symmetric Functions. - 9. 2 Polynomial Resultants. - 9. 3 Subresultants. - 9. 4 Elimination Examples. - 10 Formal Power Series. - 10. 1 Introduction. - 10. 2 Power Series Arithmetic. - 10. 3 Power Series Exponentiation. - 10. 4 Composition of Formal Power Series. - 10. 5 Reversion of Power Series. - 11Bounds on Polynomials. - 11. 1 Heights of Polynomials. - 11. 2 Uniform Coefficient Bounds. - 11. 3 Weighted Coefficient Bounds. - 11. 4 Size of a Polynomial's Zeroes. - 11. 5 Discriminants and Zero Separation. - 12 Zero Equivalence Testing. - 12. 1 Probabilistic Techniques. - 12. 2 Deterministic Results. - 12. 3 Negative Results. - 13 Univariate Interpolation. - 13. 1 Vandermonde Matrices. - 13. 2 Lagrange Interpolation. - 13. 3 Newton Interpolation. - 13. 4 Fast Fourier Transform. - 13. 5 Abstract Interpolation. - 14 Multivariate Interpolation. - 14. 1 Multivariate Dénse Interpolation. - 14. 2 Probabilistic Sparse Interpolation. - 14. 3 Deterministic Sparse Interpolation with Degree Bounds. - 14. 4 Deterministic Sparse Interpolation without Degree Bounds. - 15 Polynomial GCD's: Interpolation Algorithms. - 15. 1 Heuristic GCD. - 15. 2 Univariate Polynomials over ?. - 15. 3 Multivariate Polynomials. - 16 Hensel Algorithms. - 16. 1 m-adic Completions. - 16. 2 One Dimensional Iteration. - 16. 3 Multidimensional Iteration. - 16. 4 Hensel's Lemma. - 16. 5 Generalizations of Hensel's Lemma. - 16. 6 Zassenhaus' Formulation of Hensel's Lemma. - 17 Sparse Hensel Algorithms. - 17. 1 Heuristic Presentation. - 17. 2 Formal Presentation. - 18 Factoring over Finite Fields. - 18. 1 Square Free Decomposition. - 18. 2 Distinct Degree Factorization. - 18. 3 Finding Linear Factors. - 18. 4 Cantor-Zassenhaus Algorithm. - 19 Irreducibility of Polynomials. - 19. 1 Deterministic Irreducibility Testing. - 19. 2 Counting Prime Factors. - 19. 3 Hilbert Irreducibility Theorem. - 19. 4 Bertini's Theorem. - 20 Univariate Factorization. - 20. 1 Reductions. - 20. 2 Simple Algorithm. - 20. 3 Asymptotically Good Algorithms. - 21 Multivariate Factorization. - 21. 1 General Reductions. - 21. 2 Lifting Multivariate Factorizations. - 21. 3 Leading Coefficient Determination. - 21. 4Multivariate Polynomials over Q. - 21. 5 Bivariate Polynomials over Fields. - List of symbols. Language: English