SOLUTION OF POLYNOMIAL EQUATIONS IN ARBITRARY ORDERS

Abstract

The article deals with an algorithm of solving polynomial equations in a ring D[x], where D is an arbitrary order of field Q(ω) and ω is an algebraic integer. The algorithm develops Kurt Hensel’s idea published in 1904 which was named Hensel’s lifting lemma later. The algorithm described is based on the following theoretical results. Firstly, basis of order D expansion coefficients of the equation roots are estimated, i. e. an estimate for the polynomial equation roots height in an algebraic number field arbitrary order is derived. Secondly, an iterative formula for the corresponding polynomial congruence solution quadratic lifting modulo power of prime in the order is obtained. This formula does not contain any divisions. Thirdly, an effective bound for prime power the congruence solution needs to be lifted to obtain the exact solution of the original equation is derived. Notice that a prime p which is used for lifting needs to satisfy certain conditions for the algorithm correct work. In particular, p should not derive the original polynomial and its derivative resultant norm and also p should not derive discriminant of an algebraic integer ω. Also the algorithm complexity is decreased if it is possible to choose prime p which in addition to two previous conditions has the following property: the minimal polynomial of ω which coefficients are reduced modulo p is irreducible over finite field Fp. 4 In this case the algorithm complexity is O(m + m γi ) 3 ln m ln(max0�i�m + m3 ln(max0�i�m γi ) ln ln(max0�i�m γi ) arithmetic operations. Here m is the original polynomial degree, γi, 0 � i � m are its coefficients and γ is the algebraic numbers conjugated to γ absolute values maximum. If it is impossible to choose prime number p such that minimal polynomial of ω is irreducible 4 over Fp then the algorithm complexity is O(m + m3 ln m ln(max0�i�m γi ) + m3 ln(max0�i�m γi ) ln ln(max0�i�m γi ) + md ln ln(max0�i�m γi )) arithmetic operations. Here d is the minimal polynomial of ω irreducible factors over Fp number. The algorithm includes strategy to select a prime p to achieve lower computational complexity.