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

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

Вычислим m mod 1024 = 897, и a mod 1024 = 856. Перепишем уравнение
(4.99) в виде:

                    x2 + 1614x − 856 ≡ 0(mod 2k ).

В примере a ≡ 0(mod 4), поэтому решение существует только при x = 2y .
Подставим x = 2y в последнее уравнение:

                  4y 2 + 4 · 807x − 856 ≡ 0 (mod 2k ).

      Поделим последнее уравнение на 4:

                   y 2 + 807y − 214 ≡ 0 (mod 2k−2 ).                     (4.100)

      Рассмотрим каждую последующую степень:
      1. k=3. Заменим коэффициенты в (4.100) на их остатки по модулю 8.
Получим уравнение

                     y 2 + y ≡ 0 (mod 2),

которое выполняется для всех y .
      2. k=4. Заменим коэффициенты в (4.98) на их остатки по модулю 16.
Получим уравнение

                  y 2 + 3y − 2 ≡ 0 (mod 2),

которое выполняется при y ≡ 2 (mod 4) или y ≡ 3 (mod 4).
      3. Для последующих k > 4 корни уравнения (4.98) будем искать по
индукции.
      Любое решение должно иметь вид z = y + 2k · r , где y – решение
уравнения (4.99) для предыдущей степени, r - целое число, которое будем
искать. Подставим z = y + 2k · r в уравнение s(z) = z 2 + 807z − 214 ≡
0 (mod 2k+1 ):

                 (y + 2k · r)2 + 807(y + 2k · r) − 214 ≡ 0 (mod 2k+1 )

или
                      s(y) + 807 · 2k · r − 214 ≡ 0 (mod 2k+1 ).