Effective Polynomial Computation

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.