О решении полиномиальных уравнений в произвольных порядках

В данной статье описывается алгоритм решения полиномиальных уравнений в кольце $\mathfrak D [x]$, где $\mathfrak D$ — произвольный порядок поля $\mathbb Q (\omega)$, а $\omega$ — целое алгебраическое число. Предложенный алгоритм является развитием идеи Курта Гензеля, описанной им в 1904 году и впоследствии названной леммой Гензеля о подъеме решения полиномиального сравнения. Описываемый алгоритм основан на следующих теоретических результатах. Во-первых, оцениваются коэффициенты разложения по базису порядка $\mathfrak D$ решений уравнения, то есть выводится оценка на высоту решения полиномиального уравнения в произвольном порядке поля алгебраических чисел. Во-вторых, выписывается итерационная формула, не содержащая в себе делений, позволяющая произвести квадратичный подъем решения соответствующего сравнения по модулю степени простого числа в порядке. В-третьих, подбирается эффективная оценка на степень простого числа, до которой следует поднимать решение вышеуказанного сравнения для получения точного решения исходного уравнения.
Следует заметить, что для корректной работы алгоритма требуется выбрать простое число $p$, по которому будет производиться подъем, так, чтобы выполнялись определенные условия. А именно, $p$ не должно делить норму результанта исходного многочлена и его производной и дискриминант целого алгебраического числа $\omega$. Также вычислительная сложность алгоритма уменьшается, если удается подобрать простое число $p$, которое в дополнение к двум условиям, изложенным в предыдущем предложении, обладает тем свойством, что минимальный многочлен алгебраического числа $\omega$, все коэффициенты которого редуцированы по модулю $p$, неприводим в конечном поле из $p$ элементов. В этом случае вычислительная сложность алгоритма составляет $\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$ — степень исходного многочлена, $\gamma_i$, $0\le i\le m$ — его коэффициенты, а  — максимум модулей всех чисел, сопряженных с $\gamma$. В том же случае, когда не удается выбрать простое число $p$ так, чтобы минимальный многочлен $\omega$ был неприводим в конечном поле из $p$ элементов, вычислительная сложность алгоритма составляет $\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}$$))$ арифметических операций. Здесь $d$ — количество неприводимых сомножителей, на которые раскладывается минимальный многочлен числа $\omega$ в $\mathbb F_p$. Алгоритм, изложенный в статье, включает в себя стратегию выбора простого числа $p$ для достижения меньшей вычислительной сложности.
Библиография: 15 названий.