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

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

может быть легко решена с использованием обычного метода Гаусса.
Сложность заключается в том, что размерность системы чрезвычайно
велика и достигает величины 106 × 106 и более. Поэтому для решения
соответствующей системы ЛУ используется специальные методы решения
разреженных систем ЛУ, например, блочный метод Лантцоша (Lanszos’
Block method). Питер Монтгомери ([38]) применил его для решения СЛАУ в
методе решета числового поля. Описание этого метода можно также найти
в обзоре ([23]).
       Дадим краткое описание решения системы методом Гаусса. Алгоритм
Гаусса состоит из двух этапов. На первом этапе матрица приводится к
левотреугольному виду с нулями ниже главной диагонали, а на втором
этапе – добиваемся, чтобы нули стояли выше главной диагонали. Первый
этап метода Гаусса выполняется в цикле по строкам i матрицы системы
SystM atr[1..m, 1..k]. На i-м шаге 1 этапа сначала выбирается ведущий
элемент, отличный от 0. Если элемент SystM atr[i, i] = 1, он и будет
ведущим элементом. Если же SystM atr[i, i] = 0, то организуем цикл по
элементам i-й строки, находящимся правее SystM atr[i, i], проверяя условие
SystM atr[i, j] = 1 для i < j ≤ k . Если элемент SystM atr[i, j] =
1 существует, то переставим i и j столбцы местами, делая элемент
SystM atr[i, i] ненулевым.
       Возможна ситуация, когда такого ненулевого элемента SystM atr[i, j]
не существует. По конструкции левее SystM atr[i, i] находятся также
нули, поэтому этот случай означает, что строка i полностью нулевая.
Такую строчку можно выбросить из матрицы без ущерба для дальнейшего
вычисления.


4.5. Оценка сложности метода квадратичного решета
       Мы используем здесь оценки Померанса [47]. Пусть число ε,
принадлежащее интервалу (0, 1) таково, что радиус интервала просеивания
L оценивается величиной L + N ε . Наибольшее значение полинома
просеивания q(x) наблюдается на границах интервала [−L, L] и равно