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

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

гладким. Мощность этого множества значительно меньше радиуса L
интервала просеивания.
      Поскольку при первичном просеивании делители элементов q(xi )
не накапливаются, т.к. это требует огромного количества памяти, то
необходимо вторичное просеивание по элементам множества Smooth.
Вторичное просеивание выполняется по тому же алгоритму, что и основное,
но вместо всего интервала просеивания [−L, L] пробегаются только
элементы множества Smooth. Поэтому время выполнения этой стадии
намного меньше времени первого просеивания.
      Для хранения векторов степеней разложения элементов Smooth
необходимо определить массив V ec[1..k, 0..sz ], где константа sz равна
размеру факторной базы + 1. Элемент V ec[i, 0] могут принимать два
значения:                           (
                                        0, если q(xi ) > 0,
                     V ec[i, 0] =
                                        1, иначе.
Другие значения V ec[i, j] равны степени, в которой элемент факторной базы
FB pj входит в разложение значения q(xi ). Максимальные значения V ec[i, j]
достигаются на начальных значениях j = 1, 2 ... и не превышает log2 q(L).


4.4. Решение системы линейных уравнений
     В результате предыдущего шага была сформирована недоопределенная
система линейных уравнений с нулевой правой частью и коэффициентами
из поля F2 = {0, 1}, число уравнений m которой строго меньше числа
неизвестных k .
                   Am×k · X = 0.                                    (4.104)

      Матрица системы получена соединением столбцов, каждый из который
представляет вектор разложения j -о гладкого числа по факторной базе по
модулю 2. Система обладает как минимум k −m нетривиальными векторами
решения. Особенностью системы является сильная ее разреженность,
особенно в нижней ее части, соответствующей степеням старших простых
чисел из факторной базы (см. пример в следующем разделе). Такая система