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

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

      III. Решение системы

      Система уравнений с основной матрицей A и нулевым столбцом
свободных членов содержит 15 неизвестных и 14 уравнений, т.е. является
недоопределенной. Заменим все коэффициенты матрицы A их остатками
по модулю 2. Тогда, все коэффициенты системы примут значения либо
0, либо 1. Можно рассматривать столбцы системы, как векторы длины
14. Множество столбцов состоит из 15 вектором, которые, очевидно,
будут линейно зависимы, поэтому, можно выбрать непустое подмножество
столбцов, нетривиальная линейная комбинация которых равна нулевому
вектору. Поскольку, коэффициенты линейной комбинации равны либо 0, либо
1, то линейная комбинация является просто суммой векторов (по модулю 2).
      Коэффициенты этой линейной комбинации могут быть найдены либо
методом Гаусса, либо методом Лантцоша (см. [38]). В следующем разделе
рассмотрим пример решения системы методом Гаусса.


4.7. Пример решения системы методом Гаусса
Рассмотрим пример нахождения решения системы методом Гаусса для n =
2041. Константу m положим равной 45, тогда n = m2 + 16 и полином q(x)
равен (x + m)2 − n = x2 + 90x − 16. Определим L = 5 и вычислим значения
q(x) на интервале [-5; 5]:

         x     -5    -4      -3    -2   -1        0   1   2       3   4   5
       q(x) -441 -360 -277 -192 -105 -16 75 168 263 360 459
      Выберем факторную базу F B = {2, 3, 5, 7 } и выполним просеивание
q(x) на интервала [-5; 5] по этой факторной базе. Получим следующее
представление:

  x       -5         -4           -2         -1       0       1       2       4
 q(x) −32 · 72 −23 · 32 · 5 −26 · 3 −3 · 5 · 7 −24 3 · 52 23 · 3 · 7 23 · 32 · 5
                             Таблица 1. Гладкие числа.

      Перепишем эти разложения в виде матрицы, в которой столбец ±