Solution of polynomial equations in arbitrary orders

M. E. Zelenova

Čebyševskij sbornik, Tome 16 (2015) no. 2, pp. 117-132.

Résumé

The article deals with an algorithm of solving polynomial equations in a ring $\mathfrak D [x]$, where $\mathfrak D$ is an arbitrary order of field $\mathbb Q (\omega)$ and $\omega$ 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 $\mathfrak 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 $\omega$. 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 $\omega$ which coefficients are reduced modulo $p$ is irreducible over finite field $\mathbb F_p$. In this case the algorithm complexity is $\mathcal O(m^4+m^3\ln m\ln (\max_{0\le i\le m}$$)+m^3\ln (\max_{0\le i\le m}$$)\ln\ln(\max_{0\le i\le m}$$)$ arithmetic operations. Here $m$ is the original polynomial degree, $\gamma_i$, $0\le i\le m$ are its coefficients and is the algebraic numbers conjugated to $\gamma$ absolute values maximum. If it is impossible to choose prime number $p$ such that minimal polynomial of $\omega$ is irreducible over $\mathbb F_p$ then the algorithm complexity is $\mathcal O(m^4+m^3\ln m\ln (\max_{0\le i\le m}$$)+m^3\ln (\max_{0\le i\le m}$$)\ln\ln(\max_{0\le i\le m}$$)+m^d\ln\ln(\max_{0\le i\le m}$$))$ arithmetic operations. Here $d$ is the minimal polynomial of $\omega$ irreducible factors over $\mathbb F_p$ number. The algorithm includes strategy to select a prime $p$ to achieve lower computational complexity. Bibliography: 15 titles.

Détail

Keywords: polynomial equations, algebraic numbers, Galois group.

Bibliographie

[1] Hensel K., “Neue Grundlagen der Arithmetik”, J. Reine Angew. Math., 127 (1904), 51–84 | MR | Zbl

[2] Lenstra A. K., Lenstra H. W., Lovász L., “Factoring Polynomials with Rational Coefficients”, Mathematische Annalen, 261 (1982), 515–534 | DOI | MR | Zbl

[3] Dixon J. D., “Exact Solution of Linear Equations Using P-Adic Expansions”, Numerische Mathematik, 40 (1982), 137–141 | DOI | MR | Zbl

[4] Zelenova M. E., “Solution of Polynomial Equations in the Field of Algebraic Numbers”, Moscow University Mathematics Bulletin, 2014, no. 1, 25–29

[5] Lang S., Algebra, Mir, M., 1968, 564 pp.

[6] German O. N., Nesterenko Yu. V., Number Theoretic Algorithms in Cryptography, Akademia, M., 2012, 272 pp.

[7] Postnikov M. M., Galois Theory, GIFML, M., 1963, 220 pp.

[8] Cox D. A., Galois Theory, Wiley, Hoboken, 2012, 602 pp. | MR | Zbl

[9] Bach E., Shallit J., Algorithmic Number Theory, v. I, Efficient Algorithms, The MIT Press, Cambridge–London, 1996, 496 pp. | MR | Zbl

[10] Gallagher P. X., “The Large Sieve and Probabilistic Galois Theory”, Proceedings of Symposia in Pure Mathematics, 24, 1973, 91–101 | MR | Zbl

[11] Borevich Z. I., Shafarevich I. R., Number Theory, Nauka, M., 1972, 496 pp. | MR

[12] van der Waerden B. L., Algebra, Nauka, M., 1976, 649 pp. | MR

[13] Kurosh A G., Course of Higher Algebra, Nauka, M., 1965, 431 pp. | MR

[14] Hardy G. H., Wright E. M., An Introduction to the Theory of Numbers, Oxford University Press, Oxford, 1985, 438 pp.

[15] Zorich V. A., Mathematical Analysis, v. 1, Fazis, M., 1997, 554 pp. | MR