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

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

     один корень найден, то второй легко находится с помощью теоремы
             (p)     (p)
     Виета: r1 + r2        = 2m(modp). Предположим теперь, что для всех
                             (p)   (p)
     p ∈ F B тройки < p, r1 , r2 > уже найдены.

      Последним шагом в формировании факторной базы является
нахождение решения уравнений

             q(x) = 0(mod pk )                                      (4.97)

для степеней k > 1,        pk < B . Рассмотрим эту процедуру отдельно для
случаев p = 2 и p > 2:
      p=2. Рассмотрим два подслучая:
      a) свободный член a уравнения (4.95) нечетен. Тогда сравнение (4.97)
возможно только для нечетных x, причем если x = 2y + 1, тогда

   (2y + 1)2 + 2m(2y + 1) − a ≡ 0 mod 4 ↔ 1 + 2m − a ≡ 0 mod 4.     (4.98)

      Если последнее уравнение не выполнено, тогда уравнение (4.95) не
имеет решения при k > 1. Если сравнение (4.98) выполнено, то надо
подставить y = 2y + 1 в (4.97), поделить получившееся уравнение на 4 и
повторить те же действия с новым уравнением. Ниже мы рассмотрим пример
решения уравнения (4.97).
      b) свободный член a уравнения (4.95) четен. Тогда, сравнение (4.97)
возможно только для четных x, причем если x = 2y , тогда

     4y 2 + 4my − a ≡ 0 mod 4 ↔ a ≡ 0 mod 4.                        (4.99)

      Рассмотрим следующий пример:
     Входные данные: n = 3159302165809317095910228615234377.
              √
Выберем m ≈     n = 56207669990930215, тогда a = n − m2                 =
603298676152881520

Случай p = 2

Для наглядности предположим, что ограничивающая константа B = 1500,
тогда максимальная степень двойки, меньшая B , равна 10: 210 = 1024 < B .