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

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

представить вектором показателей степеней v = (r1 , r2 , ... rk ), k – размер
факторной базы. Например, числу 560 соответствует вектор v = (5, 0, 1, 1).
       Далее Крейтчик заметил, что можно перемножить некоторые гладкие
числа так, чтобы получить полные квадраты:
       75 × 168 × 360 × 560 = 504002 , (−192) × (−16) × 75 = 4802 .

Определение 4.1. Пара       целых    чисел   (A, B)   называется      гладкой
(относительно факторной базы F ), если:
       1. Выполняется соотношение A2 ≡ B (modn),
       2. B – раскладывается в произведение элементов из F .

Согласно этому определению, множество M = {(−2, −192), (−1, −105),
(0, −16), (2, 168), (4, 360), (5, 560)}, построенное в примере, состоит из
гладких пар.
       Как использовать гладкие пары? Заметим, что при умножении чисел,
их вектора показателей степеней складываются. Чтобы произведение гладких
чисел было полным квадратом, необходимо подобрать такую комбинацию
сомножителей, чтобы сумма векторов показателей имела только четные
координаты. Например, произведению 75 × 168 × 360 × 560 соответствует
сумма векторов (0, 1, 2, 0) + (3, 1, 0, 1) + (3, 2, 1, 0) + (5, 0, 1, 1) =
(8, 4, 4, 2).
       Вместо целочисленных координат векторов степеней и их сумм
достаточно рассматривать их остатки по модулю 2, т.е. выполнять все
вычисления в поле F2       =   {0, 1}, тогда произведение элементов M
является полным квадратом тогда и только тогда, когда вектор суммы по
модулю 2 всех векторов–показателей является нулевым вектором. Множество
всевозможных векторов размерности k над полем F2 = {0, 1} образует
линейное пространство Lk размерности k , поэтому любое множество
векторов, содержащее больше k элементов, является линейно зависимым,
и существует нетривиальная линейная комбинация таких векторов, равная
нулевому вектору. Коэффициенты этой линейной комбинации можно найти,
решая систему линейных уравнений, составленную из коэффициентов
степеней взятых по модулю 2.