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

В данной статье описывается алгоритм решения полиномиальных ура­ внений в кольце 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 для достижения меньшей вычислительной сложности.