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

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

      Поскольку коэффициенты этой линейной комбинации равны либо 0,
либо 1, то она представляет собой просто сумму некоторого подмножества
векторов. Отсюда следует тот факт, что для нахождения нетривиального
подмножества гладких чисел, произведение которых есть полный квадрат,
достаточно иметь k + 1 гладкое число, где k – размер факторной базы.
      Когда набор гладких пар, содержащий не менее k+1 элемента, найден,
то решение уравнения 4.90 можно найти, решая соответствующую систему
линейных уравнений, например, с помощью метода исключения неизвестных
Гаусса.
      В   1981   г.   Д.   Диксон   [22]   предложил   метод   факторизации,
использующий идеи Крейтчика. Однако, хотя этот метод обеспечивал
значительное преимущество по отношению к предшествующим методам,
он работал медленно, т.к. пробное деление на элементы факторной базы
занимало слишком много времени.


4.2. Метод Померанца
      В 1982 г. Карл Померанц предложил новую идею поиска гладких
чисел, используя метод, похожий на решето Эратосфена. Идея Померанца
заключалась в том, что если для простого числа p ∈ F B найден аргумент x
такой, что q(x) ≡ 0 ( mod p), то на p будут делиться все элементы q(y), где y
отличающиеся от x на аргумент, кратный p, т.е. y = x+k·p, k ∈ Z. Поэтому,
если для данного p найден корень x уравнения q(x) ≡ 0 ( mod p), то для всех
y , y ≡ x (mod p) будем также выполнено условие q(y) ≡ 0 (mod p).
      Алгоритм Померанца работает следующим образом:

  1. Выбирается некоторый числовой интервал [−L; L], называемый
     интервалом просеивания,

  2. В массив целых чисел W [−L .. L] заносятся значения полинома q(x)
     для x ∈ [−L; L],

  3. Для каждого числа p из факторной базы F B ищутся числа 0 ≤ x < p