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

Глава 4. Метод квадратичного решета                                           120

4.3. Построение факторной базы
       Общая последовательность действий в процедуре подготовки
факторной базы такова:

     I. Инициализация:

  1. Составляем множество из всех простых чисел, меньших некоторой
     верхней границы B : F B = {2, 3, 5, . . . , pk }. Верхняя граница при
     n ≈ 10100 выбирается равной 106 − 107 .

  2. Фильтруем факторную базу, оставив в F B только такие элементы p,
     для которых n является квадратичным вычетом по модулю p. Иначе
     говоря, уравнение

                     n = k 2 mod p

     должно иметь целое решение k . Такие простые p отбираются с
     помощью вычисления символа Лежандра. Сложность вычисления
     функции Лежандра имеет оценку O (log n log p) (см. [17], с. 29-31), т.е.
     полиномиальна по отношению к длине числа n.

  3. Следующий     шаг    заключается    в   формировании      генерирующего
     полинома

        q(x) = (x + m)2 − n = x2 + 2mx − a,                              (4.95)
              √
     где m = [ n] и a = n − m2 .
                                                                        (p)    (p)
  4. Потом для каждого p ∈ F B , нам нужно найти корни r1 , r2
     выражения

                 q(x) = 0(modp)                                          (4.96)

     Для небольших p это можно сделать простой подстановкой чисел
     0, 1, . . . , (p − 1)/2 в уравнение (4.96), пока решение не будет найдено.
     Для больших p алгоритм Шенкса–Тонелли (D. Shanks, Tonelli),
     описанный в разд. 1.14, позволяет найти корни за время O(log2 p). Если