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

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

5.1. Базовый алгоритм решета числового поля
     Пусть n–нечетное составное число, которое необходимо факторизовать.
Главным недостатком метода квадратичного решета заключается в том, что
значения полинома просеивания q(x) = (m+x)2 −n растут очень быстро при
увеличении аргумента x на интервале просеивания [−L; L]. Например, при
L = O(1010 ) и n = O(10100 ) значение q(x) достигает значений O(1060 ). Ясно,
что факторная база для таких чисел должна была быть также огромной.
      Революционная идея Джона Полларда состояла в предложении
заменить полином 2–й степени q(x) = (x + m)2 − n, используемый в
квадратичном решете, произвольным полиномом с целыми коэффициентами
Pd (x) степени d ≥ 3, удовлетворяющим условию Pd (m) = n для
некоторого целого m, а просеивание по множеству целых чисел Z –
просеиванием в кольце Z[θ], полученном присоединением к кольцу Z целого
алгебраического числа θ , являющегося корнем полинома Pd (x). Вместо
простых натуральных чисел соответствующая факторная база будет состоять
теперь из неразложимых простых элементов кольца целых алгебраических
чисел, а проверка делимости будет выполняться с использованием нормы
алгебраического числа. Математическая теория метода решета числового
поля строится на основе теории делимости в алгебраических числовых полях,
основные положения которой мы дадим в приложении А.
      Выигрыш в использовании такой идеи состоит, в первую очередь, в
том, что условие Pd (m) = n для некоторого целого m, накладываемое на
полином Pd (x) может быть выполнено при значительно меньших значениях
коэффициентов полинома Pd (x), по сравнению с коэффициентами полинома
q(x), используемого в методе квадратичного решета. Это влечет уменьшение
абсолютных значений полинома в области просеивания и общее увеличение
эффективности метода.

Описание этапов алгоритма

     Ниже мы дадим описание основных этапов алгоритма решета числового
числового поля, опуская детали, которые будут описаны в последующих