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

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

Для каждого ri найдем наименьшее x ∈ [−L, L], удовлетворяющее x ≡
r(mod p), и выполним следующий цикл:
       while (x ≤ L) {
       W [x] = W [x] − log p;
       x = x + p; }

      Закончив просеивание по элементам p ∈ F B , выполним просеиванию
по степеням элементов факторной базы. При этом надо помнить, что если
даже x–корень кратности k > 1, вычитание W [x] = W [x]−log p выполняется
по-прежнему как для простого корня, т.к. к моменту рассмотрения корня x
кратности k операция вычитания для W [x] уже выполнялась k − 1 раз.
      3. После завершения просеивания по степеням p получим в массиве
W [−L, L] несколько элементов, примерно равных 0 (с точностью, например,
до 1 цифры после запятой). Занесем все x со значением W [x] ≈ 0 в новый
массив Smooth, который назовем массивом гладких чисел. В нашем примере
множество Smooth будет состоять из 16 чисел:

{−224, −166, −155, −99, −77, −40, −23, −21, −13, −12, 11, 22, 32, 41, 46, 268}.
      4. Поскольку при первом просеивании мы не сохраняли данные
об элементах p, входящих в разложения q(x), то необходимо повторное
просеивание уже не по всему интервалу [−L, L], а только по элементам
множества Smooth. Это просеивание выполняется намного быстрее. В
результате будет сформирован массив V ec[1..16, 0..14], соответствующий
матрице системы. Первая координата массива V ec[i, j] равна номеру
гладкого числа из множества Smooth, а вторая координата используется
для хранения степени, в которой pj входит в разложение числа xi . V ec[i, 0]
обозначает знак q(xi ), равный 0, если q(xi ) > 0, и равный 1, в противном
случае. В нашем примере второе просеивание даст следующие результаты: