M. Mignotte, D. Stefanescu. Polynomials. An Algorithmic Approach,
Springer-Verlag, Singapore, 1999. Approx. 320pp.
ISBN: 981-4021-51-2. US$49 softcover.
This textbook gives a well-balanced presentation of the classic procedures
of polynomial algebra which are computationally relevant and some algorithms
developed during the last decade. The first chapter discusses the constrcution
and the representation of polynomials. The second chapter focuses on the
computational aspects of the analytical theory of polynomials. Polynomials
with coefficients in a finaite field are then described in chapetr three,
and the final chapter is devoted to factorization of polynomials with integral
The book is primarily aimed at graduate students taking courses in Polynomial
Algebra, with a prerequisite knowledge of set theory, usual fields and
basic algebra. Fully worked out examples, hints and references complement
the main text, and details concerning the implementation of algorithms
as well as indicators of their efficiency are provided. The book is also
useful as a supplementary text for courses in scientific computing, analysis
of algorithms, computational polynomial factorization, and computational
geometry of polynomials.
Contents: 1. An Introduction to Polynomials: Construction and
representation of polynomials; Complexity and cost; Polynomial division;
Polynomial factorization; Polynomial roots. Eliminations. Resultants; Symmetric
functions; Polynomial interpolation; Irreducinility criteria. 2. Complex
Polynomials: Polynomial size; Geometry of polynomials; Stable polynomials;
Polynomial roots inside the unit disk; Bounds for the roots; Applications
to integer polynomials; Separation of roots. 3. Polynomials with Coefficients
in a Finite Field: Finite fields; Cyclotomic polynomials; Fast Fourier
transform; Number of irreducible polynomials over a finite field; Constrcution
of irreducible polynomials over a finite field; Roots of polynomials over
finite fields; Squarefree polynomials; Berlekamp's algorithm; Niederreiter's
algorithm. 4. Integer Polynomials: Kronecker's factorization method; The
berlekamp-Zassenhaus algorithm; The LLL factorization algorithm. Bibliography;
Notation; List of Algorithms; Index.
Letter by H. Niederreiter
MR: 2000e:12001 The aim of the book is to give an introduction to some polynomial theories with particular attention to the algorithmic aspect of the problems. All the results presented regard polynomials in one indeterminate. The book is divided into four chapters, as follows.
The first chapter introduces some basic notions, including complexity of polynomial operations, polynomial division, resultants and elimination theory, interpolations and some irreducibility criteria.
Chapter two considers complex polynomials and is essentially dedicated to presenting several techniques to bound complex roots and to isolate them inside (or outside) disks of the complex plane.
The third chapter introduces the theory of polynomials over finite fields and contains the definition and some properties of cyclotomic polynomials, as well as discrete/discrete fast Fourier transform and construction of irreducible polynomials over a finite field. Successively in this chapter the authors also explain the Berlekamp and Niederreiter algorithms for factorization of polynomials with coefficients in finite fields $Z\sb p$.
Finally, the last chapter deals with the problem of factorization of polynomials with integer coefficients. In particular the authors present the Berlekamp-Zassenhaus algorithm and the LLL factorization algorithm.
This textbook is addressed to graduate students in mathematics and computer science who want to improve their knowledge
in the field of polynomial theories and computational algebra. Several topics of the book take advantage of very
recently developed techniques and in this sense the book can be a good source for the state of the art in the subjects
it presents. Each section of the book is integrated with several exercises with different levels of difficulty.
Reviewed by Alessandro Logar
- ZbL: This book is devoted to the study of polynomials and includes several relevant
algorithms (some of them classic, others more recent) with detailed analysis of their algebraic
complexity. The book is structured in four chapters. \par The first begins with the formal definition
of the ring of polynomials and with two different ways of representing polynomials: dense and sparse
form. There is a study of the complexity of polynomial operations using both ways of coding. A few
basic definitions and facts on polynomials are exposed (divisibility, Euclidean algorithm, gcd,
factorization, roots). Some notions of elimination theory (resultant, Bezoutian) and of polynomial
interpolation are given. The chapter ends with some irreducibility criteria in one and several
variables. \par The second chapter is based in the analytic theory of complex polynomials: the
authors define different polynomial sizes (norm, Mahler measure, length and height) and give
upper bounds for factors of a given polynomial. Then, many interesting results on location of
roots in the complex plane are shown and finally these results are applied to integer polynomials.
In the third chapter, they present the theory of finite fields and cyclotomic polynomials in order
to show how the discrete fast Fourier transform gives a fast algorithm to multiply polynomials.
After some results on irreducible polynomials over finite fields, both Berlekamp's algorithm and
Niederreiter's algorithm for factorization of polynomials over finite fields are thoroughly discussed.
In the last chapter, three algorithms to give the factorization of polynomials over the ring of integers are
described: Kronecker's factorization method, the Berlekamp-Zassenhaus algorithm and the Lenstra-Lenstra-Lovasz
(LLL) algorithm which shows that factorization of polynomials over the ring of integers can be performed
in polynomial time.
The book is almost self-contained and the exposition is clear but a certain background
in algebra is needed. There are many interesting exercises at the end of each section, some of them extracted of
recent research papers.
Reviewed by Juan Sabia