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

                                                                             115

4. Метод квадратичного решета
      Метод квадратичного решета занимает вторую строчку в списке самых
быстрых алгоритмов факторизации, уступая только методу решета числового
поля. Рассмотрим основные идеи этого метода.


4.1. Идея Мориса Крейтчика и алгоритм Диксона
      В 20-х г. XX столетия Морис Крейтчик (Maurice Kraitchik), обобщая
идею Ферма, предложил вместо пар чисел, удовлетворяющих уравнение A2 −
B 2 = n (2.20), искать пары чисел, удовлетворяющих более общему уравнению

              A2 ≡ B 2 (mod n)                                             (4.90)

Крейтчик заметил, что многие из чисел q(x) в (2.21) раскладываются
в произведение небольших простых чисел (т.е. являются гладкими по
современной терминологии). Рассмотрим пример из статьи Померанца [46]:
      Пример. Пусть число n = 2041, которое требуется разложить.
Ближайшим к n числом, являющимся полным квадратом, является m = 45,
m2 = 2025. Рассмотрим последовательность пар чисел {x; q(x)}, где

             q(x) = (m + x)2 − n,                                          (4.91)

а x принимает близкие к 0 значения:
{(−2; −192), (−1; −105), (0; −16), (1; 75), (2; 168), (3; 263), (4; 360), (5; 459),
(6; 560)}.
      Можно заметить, что вторые координаты некоторых из этих пар
разложимы в произведение небольших простых чисел:
−192 = −26 × 3, −105 = −3 × 5 × 7, −16 = −24 , 75 = 3 × 52 , 168 =
23 × 3 × 7, 360 = 23 × 32 × 5, 560 = 25 × 5 × 7.
      Выберем множество небольших простых чисел и назовем его
факторной базой F B = {2, 3, 5, 7}. Любое целое число, разложимое в
произведение множителей из факторной базы, назовем гладким относительно
этой факторной базы. Таким образом, перечисленные выше числа являются
гладкими. Когда факторная база выбрана, любое гладкое число можно