О РЕШЕНИИ ПОЛИНОМИАЛЬНЫХ УРАВНЕНИЙ В ПРОИЗВОЛЬНЫХ ПОРЯДКАХ

В данной статье описывается алгоритм решения полиномиальных ура­ внений в кольце D[x], где D – произвольный порядок поля Q(ω), а ω – це­ лое алгебраическое число. Предложенный алгоритм является развитием идеи Курта Гензеля, описанной им в 1904 году и впоследствии названной леммой Гензеля о подъеме решения полиномиального сравнения. Описы­ ваемый алгоритм основан на следующих теоретических результатах. Во­ первых, оцениваются коэффициенты разложения по базису порядка D решений уравнения, то есть выводится оценка на высоту решения поли­ номиального уравнения в произвольном порядке поля алгебраических чи­ сел. Во-вторых, выписывается итерационная формула, не содержащая в себе делений, позволяющая произвести квадратичный подъем решения со­ ответствующего сравнения по модулю степени простого числа в порядке. В-третьих, подбирается эффективная оценка на степень простого числа, до которой следует поднимать решение вышеуказанного сравнения для получения точного решения исходного уравнения. Следует заметить, что для корректной работы алгоритма требуется выбрать простое число p, по которому будет производиться подъем, так, чтобы выполнялись определенные условия. А именно, p не должно делить норму результанта исходного многочлена и его производной и дискрими­ нант целого алгебраического числа ω. Также вычислительная сложность алгоритма уменьшается, если удается подобрать простое число p, которое в дополнение к двум условиям, изложенным в предыдущем предложе­ нии, обладает тем свойством, что минимальный многочлен алгебраиче­ ского числа ω, все коэффициенты которого редуцированы по модулю p, неприводим в конечном поле из p элементов. В этом случае вычислитель­ 4 ная сложность алгоритма составляет O(m + m3 ln m ln(max0�i�m γi ) + m3 ln(max0�i�m γi ) ln ln(max0�i�m γi ) арифметических операций. Здесь m – степень исходного многочлена, γi, 0 � i � m – его коэффициенты, а γ – максимум модулей всех чисел, сопряженных с γ. В том же случае, когда не удается выбрать простое число p так, чтобы минимальный мно­ гочлен ω был неприводим в конечном поле из p элементов, вычислитель­ 4 ная сложность алгоритма составляет 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 )) арифмети­ ческих операций. Здесь d – количество неприводимых сомножителей, на которые раскладывается минимальный многочлен числа ω в Fp. Алго­ ритм, изложенный в статье, включает в себя стратегию выбора простого числа p для достижения меньшей вычислительной сложности. 

полиномиальные уравнения, алгебраические числа, группа Галуа

1. Hensel K. Neue Grundlagen der Arithmetik // J. Reine Angew. Math. 1904. Vol. 127. P. 51–84.

2. Lenstra A. K., Lenstra H.W., Lov´asz L. Factoring Polynomials with Rational Coefficients // Mathematische Annalen. 1982. Vol. 261. P. 515–534.

3. Dixon J. D. Exact Solution of Linear Equations Using P-Adic Expansions // Numerische Mathematik. 1982. Vol. 40. P. 137–141.

4. Зеленова М. Е. Решение полиномиальных уравнений в поле алгебраических чисел // Вестн. Моск. ун-та. Cер. 1. Матем., мех. 2014. № 1. С. 25–29.

5. Ленг С. Алгебра. М.: Мир, 1968. 564 с.

6. Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. М.: Академия, 2012. 272 с.

7. Постников М. М. Теория Галуа. М.: ГИФМЛ, 1963. 220 с.

8. Cox D. A. Galois Theory. Hoboken: Wiley, 2012. 602 p.

9. Bach E., Shallit J. Algorithmic Number Theory, vol. I: Efficient Algorithms. Cambridge, London: The MIT Press, 1996. 496 p.

10. Gallagher P. X. The Large Sieve and Probabilistic Galois Theory // Proceedings of Symposia in Pure Mathematics. 1973. Vol. 24. P. 91–101.

11. Боревич З. И., Шафаревич И. Р. Теория чисел. М.: Наука, 1972. 496 с.

12. ван дер Варден Б. Л. Алгебра. М.: Наука, 1976. 649 с.

13. Курош А. Г. Курс высшей алгебры. М.: Наука, 1965. 431 с.

14. Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. Oxford: Oxford University Press, 1985. 438 p. 15. Зорич В. А. Математический анализ, т. 1. М: ФАЗИС, 1997. 554 с.