Mathematics for Computer Algebra

This book corresponds to a mathematical course given in 1986/87 at the University Louis Pasteur, Strasbourg. This work is primarily intended for graduate students. The following are necessary prerequisites : a few standard definitions in set theory, the definition of rational integers, some elementary facts in Combinatorics (maybe only Newton's binomial formula), some theorems of Analysis at the level of high schools, and some elementary Algebra (basic results about groups, rings, fields and linear algebra). An important place is given to exercises. These exercises are only rarely direct applications of the course. More often, they constitute complements to the text. Mostly, hints or references are given so that the reader should be able to find solutions. Chapters one and two deal with elementary results of Number Theory, for example : the euclidean algorithm, the Chinese remainder theorem and Fermat's little theorem. These results are useful by themselves, but they also constitute a concrete introduction to some notions in abstract algebra (for example, euclidean rings, principal rings ... ). Algorithms are given for arithmetical operations with long integers. The rest of the book, chapters 3 through 7, deals with polynomials. We give general results on polynomials over arbitrary rings. Then polynomials with complex coefficients are studied in chapter 4, including many estimates on the complex roots of polynomials. Some of these estimates are very useful in the subsequent chapters.

1 Elementary Arithmetics.- 1. Representation of an integer in basis B1.- 1. Lexicographical order.- 2. Development in basis B, existence.- 3. Prom development to number.- 4. Prom number to development in basis B.- 5. Case of general rational numbers.- 6. Comparing two numbers.- 2. Addition.- 1. Case of two positive numbers.- 2. Case of two numbers of any sign.- 3. Subtraction.- 4. Multiplication.- 5. Euclidean division.- 1. Existence.- 2. Computation.- 6. The cost of multiplication and division.- 1. The cost of multiplication.- 2. The cost of division.- 7. How to compute powers.- 1. First algorithm.- 2. Second algorithm.- 3. One application.- 4. Complexity of this problem.- 8. The g.c.d..- 1. Existence. Relation of Bézout. Theorem of Euclid-Gauss.- 2. How to compute the g.c.d..- 3. The cost of the algorithm of Euclid.- 4. The l.c.m..- 9. The group G (n).- 1. Definition.- 2. The theorem of Euler.- 3. Computation of the inverse in G (n).- 4. Computation of the coefficients of the relation of Bézout.- 10. The Chinese remainder theorem.- 1. The theorem.- 2. Constructive proof.- 3. Effective computations.- 11. The prime numbers.- 2 Number Theory, Complements.- 1. Study of the group G(n).- 1. Some lemmas on finite groups.- 2. Application to G(p).- 3. Structure of G(pk), k ? 2, p odd prime.- 4. Structure of G (2k).- 5. Structure of G (n).- 2. Tests of primality.- 1. A general theorem.- 2. A simple test of primality.- 3. Elementary tests.- 4. Statistics on G (n).- 3. Factorization of rational integers.- 1. Methods by successive divisions.- 2. Method of Fermat.- 3. Method of Sherman Lehman.- 4. Pollard’s rho method.- 3 Polynomials, Algebraic Study.- 1. Definitions and elementary properties.- 1. First definitions.- 2. Elementary arithmetic operations.- 3. Notions of degree.- 4. Case of an integral domain.- 2. Euclidean division.- 1. Monic polynomials.- 2. Euclidean division.- 3. The case of a field.- 4. Pseudo-division.- 3. The Chinese remainder theorem.- 4. Factorization.- 1. Case of a field.- 2. Case of a factorial ring.- 5. Polynomial functions.- 1. Definition.- 2. Roots of a polynomial.- 3. Multiplicity of a root.- 4. Derivatives and roots.- 5. Taylor’s formula.- 6. The resultant.- 7. Companion matrix.- 8. Linear recursive sequences.- 4 Polynomials with complex coefficients.- 1. The theorem of d’Alembert.- 1. Statement.- 2. Analytic properties.- 3. Demonstration of the theorem.- 4. Irreducible real polynomials.- 2. Estimates of the roots.- 1. Principle of the demonstration.- 2. An analytic lemma.- 3. Bounds for the roots.- 3. The measure of a polynomial.- 1. Definition.- 2. An algebraic lemma.- 3. An upper bound for M(P).- 4. Other upper bounds.- 5. Analytic results.- 6. A method for the computation of M(P).- 7. An example of the evaluation of M (P).- 4. Bounds for size of the factors of a polynomial.- 1. Definitions.- 2. Upper bounds for the factors in the case of a single variable.- 3. Definition of the measure in the case of several variables.- 4. Bounds for the factors of a polynomial, case of several variables.- 5. An example in the case of one variable.- 5. The distribution of the roots of a polynomial.- 1. An upper bound for the number of real roots.- 2. Distribution of the arguments of the roots of a polynomial.- 6. Separation of the roots of a polynomial.- 1. Notations.- 2. A lower bound for sep(P).- 3. Other lower bounds for the distance between two roots.- 4. Use of Galois properties.- 5. An example.- 5 Polynomials with real coefficients.- 1. Polynomials irreducible over ?.- 2. The theorem of Rolle.- 1. The theorem of intermediate values.- 2. The theorem of Rolle.- 3. Estimates of real roots.- 1. The rule of Newton.- 2. The rule of Lagrange and MacLaurin.- 3. A special case of the rule of Descartes.- 4. The rule of Cauchy.- 5. An example of an estimation of the real roots of a polynomial.- 4. The number of zeros of a polynomial in a real interval.- 1. The rule of Sturm.- 2. The theorem of Budan-Fourier.- 3. The rule of Descartes.- 4. Case of the polynomials whose all roots are real.- 5. A detailed example.- 6. Vincent’s theorem.- 5. Equations whose roots have a negative real part.- 6/Polynomials over finite fields.- 1. Finite fields.- 1. General results.- 2. The operations in a finite field.- 3. Determination of a primitive element of H*.- 4. Determination of z such that Wq—Hp[z].- 5. An example: H8.- 2. Statistics on Hq[X].- 1. The function of Möbius.- 2. Counting irreducible polynomials.- 3. Number of squarefree polynomials.- 4. Study of the number of irreducible factors of a polynomial.- 3. Factorization into a product of squarefree polynomials.- 1. Definitions and generalites.- 2. Case of characteristic zero.- 3. Case of non zero characteristic.- 4. Algorithms of decomposition into a product of squarefree polynomials.- 4. Factorization of the polynomials over a finite field.- 1. Determination of the number of irreducible factors.- 2. Complete factorization.- 3. Cost of the algorithm.- 4. Case where q is large.- 5. Decomposition into a product of irreducible factors of given degree.- 6. The method of MacEleice.- 5. Search for the roots of a polynomial in a finite field.- 1. A first reduction.- 2. Case of the polynomials which split completely in Hq.- 3. Solution of the binomial equation Xd= a.- 7 Polynomials with integer coefficients.- 1. Principles of the algorithms of factorization.- 1. Existence of an algorithm of factorization.- 2. The algorithm of Kronecker.- 3. The principle of modern algorithms.- 2. The choice of the prime modulus.- 3. Refining the factorization.- 1. The bound B.- 2. Hensel’s lemma.- 4. Berlekamp’s method of factorization.- 5. The algorithm L3.- 1. Lattices.- 2. Orthogonalization of Gram-Schmidt.- 3. Reduced basis.- 4. Algorithm of reduction.- 5. Cost of the algorithm.- 6. Factors of polynomials and lattices.- 7. The algorithm of factorization.- Index of Names.