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

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

значениям символа Лежандра, вычисленным по формуле (5.137). Отметим,
что компонента для знака F1 (a, b) отсутствует, поскольку полученное
произведение будет полным квадратом.

Решение системы линейных уравнений

Само решение системы не отличает от решения в случае метода
квадратичного решета (см.разд.4.4). Опять можно выполнить либо
использование стандартной процедуры исключения переменных методом
Гаусса, либо использовать гораздо более сложный метод Лантцоша (см.[38]).
Мы не будем здесь останавливаться на особенностях решения системы, а
сделаем предположение о том, что решение уже найдено. Выпишем такое
решение для нашего примера n = 45113, взятого из диссертации М.Бриггса
[12].

                                                                       Таблица 4
                Элементы множества M , дающие решение системы

                     (a, b)     (a, b)     (a, b)   (a, b)   (a, b)
                      (1,1)    (-104,1)    (8,3)    (43,6) (-856,11)
                     (-3,1)     (-3,2)    (-48,5)   (8,7)
                     (-13,1)   (-25,2)    (-54,5) (-11,7)

        Обозначим через         γ(x)      многочлен, равный произведению всех
многочленов a − bx, где пара (a, b) принадлежит найденному множеству
решений S :
         Y
γ(x) =         (a−bx) = 2051543129764485x2 +15388377355799440x+
         x∈S

        +24765692886531904                                                (5.138)


        Сделаем теперь несколько замечаний о найденном решении. Пока что
мы можем только утверждать, что норма многочлена N r(γ(x)) является
полным квадратом. Очевидно, если многочлен γ(x) = α2 (x) является