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

Глава 5. Метод решета числового поля                                   154

Построение алгебраической базы характеров

Построение   третьей   факторной     базы,   состоящей   из   квадратичных
характеров, выполняется также, как и алгебраической. Выбирается
новый ограничитель B3 > B2 и рассматриваются все простые числа
от B2 до B3 . Для рекордных разложений B3 выбирается так, чтобы в
интервал [B2 , B3 ] попало 104 − 105 простых чисел. Выбор размерности
B3 определяет степень уверенности в том, что найденное в результате
просеивания полином является полным квадратом (см. Buchler et alt. [13]).

      В нашем примере возьмем B3 = 109, и построим квадратичную
факторную базу способом, описанным ранее (см.табл.2).
                                                                 Таблица 2
                Факторная база квадратичных характеров
                         (p, r)    (p, r)    (p, r)
                        (107,4) (107,80) (109,99)
                        (107,8) (109,52)

Расчет необходимого количества гладких пар

      Вычислим теперь суммарный объем трех факторных баз s = 10 +
23 + 5 = 38. Значит, область просеивания должна содержать не менее
40 элементов (добавляется один столбец для хранения знака числа a −
bm плюс дополнительная единица для того, чтобы матрица системы была
недоопределена и имела ненулевое решение (см.разд. 4.4). Полученное
значение влияет на размер области просеивания, в которой ищутся гладкие
пары, и определяет размер системы линейных уравнений, формируемой для
нахождения решения.


5.3. Просеивание в решете числового поля
     Процедура просеивания в методе решета числового поля, в целом, мало
чем отличается от аналогичной процедуры в методе квадратичного решета.