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

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

      Процедура просеивания является самой затратной по времени частью
алгоритма квадратичного решета. В ходе ее выполнения ищутся пары чисел
(A, B), удовлетворяющих
                                A2 ≡ B mod n.                         (4.93)

      Размер факторной базы является одним из ключевых параметров
алгоритма просеивания, определяющих его эффективность. Если ее размер
является слишком маленьким, то гладкие числа будут попадаться очень
редко или не будут попадаться вообще. При недостаточном размере
факторной базы приходится выбирать большой радиус L интервала
просеивания, что влечет увеличение общего времени вычисления.
      Если же размер факторной базы слишком велик, то требуется
поиск большого числа гладких чисел, что также увеличивает общее время
вычисления. Отметим, что для разложения 129-значного числа создателей
RSA потребовалась факторная база, содержащая 524338 простых чисел.
      Обозначим размер факторной базы через k . Для разложения числа
n, необходимо отыскать k 0 гладких пар (A; B), k 0 ≥ k + 2. После
этого формируется система линейных уравнений размерности k × k 0 с
коэффициентами из поля F2 = {0, 1} и нулевым столбцом свободных
членов. Система – не доопределена и потому имеет нетривиальное решение,
представляющее множество M первых аргументов гладких пар (x, q(x)).
Тогда пара (A, B), удовлетворяющая уравнению (4.90), находится как
           Y                          Y
      A=         (x + m) mod n, B =         q(x) mod n.               (4.94)
           x∈M                        x∈M

      Теперь     делители   p   исходного    n   можно    найти,   вычисляя
Н.О.Д.(n, A ± B). В некоторых случаях оба найденных делителя
оказываются тривиальными (равными 1 или n), тогда нужно искать другое
решение системы и новую пару (A, B). Опишем процедуру построения
факторной базы более подробно.