Polynomials: An Algorithmic Approach (Discrete Mathematics and Theoretical Computer Science)

✍ Scribed by Maurice Mignotte D. Stefanescu M. Mignotte

• Publisher: Springer
• Year: 1999
• Tongue: English
• Leaves: 316
• Edition: 1
• Category: Library

✦ Synopsis

Book by Mignotte, Maurice, Stefanescu, Doru

✦ Table of Contents

Title
Introduction
Contents
1 An Introduction to Polynomials
1.1 Construction and Representation of Polynomials
1.1.1 Construction of polynomials
1.1.2 Representation of polynomials
1.2 Complexity and Cost
1.2.1 Complexity
1.2.2 Cost of polynomial operations
1.3 Polynomial Division
1.3.1 Divisibility
1.3.2 Unique factorization domains
1.3.3 The Euclidean division algorithm
1.3.4 Existence of gcd
1.3.5 Construction of gcd
1.3.6 Pseudo-division and polynomial remainder sequences
1.4 Polynomial Factorization
1.4.1 Polynomials over factorial rings
1.5 Polynomial Roots. Elimination. Resultants
1.5.1 Polynomial roots
1.5.2 Elimination theory. Resultants
1.5.3 The abridged method of Bezout
1.5.4 Jacobi's version
1.5.5 Cauchy's contribution
1.5.6 The companion matrix
1.6 Symmetric Functions
1.7 Polynomial Interpolation
1.7.1 Lagrange interpolation
1.7.2 Lagrange-Hermite interpolation
1.7.3 Newton interpolation
1.7.4 Taylor interpolation
1.7.5 Newton-Hermite interpolation
1.7.6 Finite differences
1.7.7 Chinese remainder theorem
1.8 Irreducibility Criteria
1.8.1 Irreducible polynomials in one variable
1.8.2 Irreducible polynomials in many variables
1.8.3 Generalized difference polynomials
2 Complex Polynomials
2.1 Polynomial Size
2.1.1 Norm
2.1.2 Measure
2.1.3 Length and height of a polynomial
2.1.4 Upper bounds for factors
2.2 Geometry of Polynomials
2.2.1 Location of polynomial roots
2.2.2 Apolar polynomials
2.3 Stable Polynomials
2.4 Polynomial Roots Inside the Unit Disk
2.5 Bounds for the Roots
2.5.1 Inclusion radii
2.5.2 Disks containing no roots
2.5.3 Disks containing at least one root
2.5.4 Disks containing at least a prescribed number of roots
2.6 Applications to Integer Polynomials
2.6.1 An irreducibility test
2.6.2 Primes and polynomial irreducibility
2.7 Separation of Roots
3 Polynomials with Coefficients in a Finite Field
3.1 Finite Fields
3.1.1 Construction of finite fields
3.1.2 Representation of elements of finite fields
3.2 Cyclotomic Polynomials
3.2.1 Definition of cyclotomic polynomials
3.2.2 Mobius inversion formula
3.2.3 Factorization of cyclotomic polynomials
3.3 Fast Fourier Transform
3.3.1 Discrete Fourier transform
3.3.2 Discrete fast Fourier transform
3.3.3 Fast multiplication of polynomials
3.4 Number of Irreducible Polynomials over a Finite Field
3.5 Construction of Irreducible Polynomials Over a Finite Field
3.5.1 Exponents of polynomials over a finite field
3.5.2 Irreducibility of binomials
3.5.3 Artin-Schreier polynomials
3.6 Roots of Polynomials Over Finite Fields
3.7 Squarefree Polynomials
3.7.1 Definition of squarefree polynomials
3.7.2 Factorization into a product of squarefree polynomials
3.7.3 The number of squarefree polynomials
3.8 Berlekamp's Algorithm
3.8.1 Factorization of polynomials over finite fields
3.8.2 Polynomial factorization over Fp
3.8.3 Polynomial factorization over Wq
3.8.4 Description of the algorithm
3.8.5 Berlekamp's method over large fields
3.9 Niederreiter's Algorithm
3.9.1 Factorization of squarefree polynomials
3.9.2 Factorization of nonsquarefree polynomials
3.9.3 Factorization over F2
3.9.4 The refinement by Gottfert
3.9.5 Hasse-Teichmiiller derivatives method
4 Integer Polynomials
4.1 Kronecker's Factorization Method
4.1.1 Kronecker's algorithm
4.1.2 Kronecker-Hausmann algorithm
4.1.3 A bound for factors
4.2 The Berlekamp-Zassenhaus Algorithm
4.2.1 Modern methods of factorization in Z[Õ]
4.2.2 Size of factors
4.2.3 Hensel's lemma
4.2.4 Reconstruction of factors over the integers
4.3 The LLL Factorization Algorithm
4.3.1 Reduced bases for lattices
4.3.2 Reduced lattices
4.3.3 Basis reduction algorithm
4.3.4 Polynomial factorization and lattices
4.3.5 The factorization algorithn
4.3.6 Cost of the algorithm
Bibliography
Notation
List of Algorithms
Name Index
Subject Index