Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 161 стр.

Глава 5. Метод решета числового поля                                  162

полиномов не представляет особой трудности, и выполняется примерно
такими же методами, как вычисление квадратного корня в кольце целых
чисел или конечных полях, например, с использование алгоритма Шенкса–
Тоннелли (см.разд.1.14).
      В случае рекордных значений факторизуемых чисел, значения
коэффициентов полиномов достигают нескольких миллионов цифр, и
задача извлечения корня становится чрезвычайно сложной и трудоемкой
задачей, сравнимой по затратам ресурсов с задачей просеивания. Если
же степень полинома просеивания становится больше 7, то время,
затрачиваемое на вычисление корня, превышает время просеивания.
Поэтому нахождение эффективного алгоритма вычисления квадратного
корня играет чрезвычайно важную роль в решете числового поля. Мы
рассмотрим здесь два основных метода, используемых в практике GNFS.

Вычисление корня путем редукции к подполям

Это метод был предложен в работе 1993 г. Жаном Ковейном (Jean
M. Couveignes) [20] (см.также П.Монгомери [39]). Суть метода состоит в
том, что вычисление квадратного корня выполняется в конечных полях
по нескольким различным простым модулям p. Если рассматриваемое p
является инертным, т.е. многочлен g(x) mod p (т.е. многочлен, полученный
из g(x) путем замены всех его коэффициентов их остатками по модулю p)
неприводим в поле Fp , и αp2 (x) = g(x) mod p, тогда коэффициенты искомого
корня из полинома g(x) совпадут с коэффициентами αp (x) по модулю p.
Вычислив несколько таких частичных корней по различным модулям, можно
потом восстановить полный полином α(x) с помощью китайской теоремы
об остатках. Число различных p должно быть таким, чтобы произведение
всех этих p превышало максимальный по абсолютной величине коэффициент
полинома α(x). Ниже мы дадим пример вычисления корня из полинома по
методу Ковейна для n = 45113.
      Метод Ковейна работает только для нечетных степеней d полинома
f1 (x). Кроме того, в редких случаях возможна ситуация, когда для
многочлена нет подходящих простых чисел p, для который g(x) mod p