Skip to main content

Über dieses Buch

This book deals with several topics in algebra useful for computer science applications and the symbolic treatment of algebraic problems, pointing out and discussing their algorithmic nature. The topics covered range from classical results such as the Euclidean algorithm, the Chinese remainder theorem, and polynomial interpolation, to p-adic expansions of rational and algebraic numbers and rational functions, to reach the problem of the polynomial factorisation, especially via Berlekamp’s method, and the discrete Fourier transform. Basic algebra concepts are revised in a form suited for implementation on a computer algebra system.



1. The Euclidean algorithm, the Chinese remainder theorem and interpolation

Let m be an arbitrary integer number (positive, negative or zero), n a positive integer, and let
$$ \dots, \hbox{---} kn, ...,\hbox{---} 2n,\hbox{---} n,0,n,2n,\dots, kn, ... $$
the set of multiples of n. There exist two consecutive terms of this sequence, qn and (q + 1)n, such that:
$$ qn\le m<\left(q+1\right)n. $$
Antonio Machì

2. p-adic Series Expansions

In this section we shall deal with the expansion of a rational number as a series of powers of a not necessarily prime number p ≥ 2. As we shall see, the techniques we shall use extend to rational numbers the way we write a positive integer number in base p. In that case, the expansion is finite, that is, we have a polynomial in p with coefficients at least 0 and at most p – 1; here the expansion is infinite, that is, we have a power series in p, with the same range for the coefficients.
Antonio Machì

3. The resultant

Let f = f (x) and g = g(x) be two polynomials of degree n and m, respectively. If f and g have a non-constant factor d = d(x) in common, then
$$ \begin{array}{cc} f=dk, & \partial k<n, \\ g=dh, & \partial h<m\hbox{,} \end{array} $$
for some polynomials k and h. From this follows
$$ d=\frac{f}{k}=\frac{g}{h} $$
$$ fh=gk $$
Conversely, suppose that there exist polynomials k and h, with ∂k < n and ∂h < m, such that (3.1) is satisfied. Dividing h and k by (h, k), (3.1) becomes fh 1 = gk 1, with (h 1, k 1 ) = 1. Then k 1 divides f, f = k 1 w and hence gk 1 = fh 1 = k 1 wh 1, so g = h 1 w. Moreover, ∂w = ∂f – ∂k 1 and ∂k 1 ≤ ∂k < ∂f, so ∂w > 0. Substituting –k for k, (3.1) may be rewritten as:
$$ fh+gk=0 $$
Antonio Machì

4. Factoring polynomials

In this first section of the chapter we consider a classical method, due to Kronecker, for factoring an integer polynomial. We should mention at the outset that the interest of the method does not lie in its applicability (it is not really efficient, even for polynomials of degree as low as five) but rather in its existence. Indeed, it affords an algorithm that in finitely many steps allows one to establish whether a polynomial is reducible or not, and if the answer is in the positive it yields the factorisation into irreducible factors. In other words, it allows one to state that the problem of factoring an integer polynomial is decidable.
Antonio Machì

5. The discrete Fourier transform

The n-th roots of unity are the roots of the polynomial x n — 1 in the complex field. We know that they are all distinct because the polynomial is coprime with its derivative, and that they are all powers of one of them, a primitive root ω = e 2πi/n :
$$ 1,w,{w}^2,\dots, {w}^{n-1}, $$
with w n = 1. (Recall that the primitive roots w k are those for which (k, n) = 1, so that their number is φ(η), where φ is Euler’s function.) Since 1 is a root of x n −1, this polynomial is divisible by x−1, with quotient 1+x+x 2 +…+x n−1, and therefore all the w k , with k ≠ 0 (or, actually, k ≠ 0 mod n), satisfy the equation:
$$ 1+x+{x}^2+\cdot \cdot \cdot +{x}^{n-1}=0. $$
In particular, for x = w we see that the sum of all the n-th roots of unity is zero, 1 + w + w 2 +···+ w n-1 = 0. Moreover, since |w| = 1, we have |w| k = 1, so that \( {w}^k{\overline{w}}^k={\left|{w}^k\right|}^2=1 \), from which
$$ {\overline{w}}^k=\frac{1}{w^k}={w}^{-k}. $$
We use formulas (5.1) and (5.2) to prove the following theorem; despite its simplicity, it will be of fundamental importance for the entire discussion.
Antonio Machì


Weitere Informationen

Premium Partner