**Описание:** |
1. introduction
The purpose of this paper is to introduce the norm decomposition which enables us to compute the roots of a monic irreducible imprimitive polynomial / £ Q[i] by solving polynomial equations of lower degree. We call an irreducible polynomial / imprimitive if the number field generated by a root of / contains non-trivial subfields. We will see that for each subfield there exists a norm decomposition. The norm decomposition generalizes the functional (Kozen and Landau, 1989) and homogeneous bivariate decompositions (von zur Gathen and Weiss, 1995). There exist imprimitive polynomials having neither a functional nor a homogeneous bivariate decomposition, but which do have a norm decomposition. Furthermore, the computing times by our algorithm are much shorter than the ones for a homogeneous bivariate decomposition.
If a functional decomposition / = g(h) with g,h £ Q[i] exists we can calculate the roots /?i, .. . , /3m of g, and then the roots ofh — Д (1 < г < т) in order to obtain the roots of /. Note that there are very efficient algorithms to compute functional decompositions.
In the homogeneous bivariate decomposition, the polynomial / is written in the form / = g(hi,h,2) where g £ Q[t, u] is homogeneous and hi,h,2 £ Q[t\- A drawback of the known algorithms for computing a homogeneous bivariate decomposition is that they require an expensive factorization of the polynomial / in K[t], where К is the number field generated by a root of /. If / has a homogeneous bivariate decomposition then / = h2ng{j^L), where g(t) = g(t,l) and m = deg(g). As / is irreducible we obtain the roots of / by first computing the roots /?i, .. . , /3m of g and then the roots of the polynomials hi — /3j/i2 (1 < i < m).
It is well known that the existence of subfields Q(/3) С Q(a) (Dixon, 1990; Lazard and Valibouze, 1993; Hulpke, 1995; Casperson et al., 1996; Kliiners and Pohst, 1997) is equivalent to / | g(h) where f,g,h £ |