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

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

     такие, что выполняется сравнение

                   q(x) ≡ 0 mod p                                 (4.92)

     Отметим, что это уравнение может иметь либо 2 решения, либо ни
     одного.

  4. Для каждого решения x уравнения (4.92) в цикле просматриваются
     числа вида xk = x + kp из интервала [−L; L], k ∈ Z, и выполняется
     деление элементов W [xk ] на p.

      Процедура повторяется для всех чисел p из факторной базы и
их степеней pk < B , ограниченных сверху границей B . В результате
выполнения процедуры просеивания некоторые элементы W [x] массива W
станут равными ±1. Соответствующие пары (x, q(x)) являются гладкими.
Для надежного нахождения нетривиального решения уравнения (4.90)
необходимо, что число найденных гладких пар превышало, по-крайней
мере, на 1 размер факторной базы. Тогда из коэффициентов разложения
гладких чисел на элементы факторной базы можно составить систему
недоопределенную систему линейных уравнений, которая будет иметь
нетривиальное решение.
      Следует отметить, что наличие нетривиального решения гарантирует
нам только нахождение пары натуральных чисел (A; B), удовлетворяющих
(4.90). Однако не все пары такого рода дают искомое решение, поэтому для
надежности получения нетривиальных делителей n число гладких чисел
должно быть больше размерности факторной базы на число k > 1, например,
на k = 3 или k = 4.
      Дополнительным      достоинством   метода    Померанца    явилась
возможность распараллеливания вычисления и запуска алгоритма для
одновременного просеивания на нескольких компьютерах. Метод Померанца
получил название метода квадратичного решета (the Quadratic Sieve).
Используя этот метод, в 1994 г. Аткинс, Граф, Лейланд и Ленстра сумели
разложить 129-значное число, предложенное создателями RSA.