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

Глава 2. Простые алгоритмы факторизации                                            78

взаимно–просты,

       (a, b, ac)2 ∼ (a2 , b, c)                                                (2.53)

      Если в квадратичной форме f = (a, b, c2 ), третий коэффициент
является полным квадратом, то такую форму будем называть квадратной
(square). Из квадратной формы f можно извлечь квадратный корень. Для
вычисления корня заменим форму f на эквивалентную ей смежную форму
f ∼ (c2 , −b, a), потом извлечем квадратный корень по формулам (2.53).
Получим:


           1/2
                     p                    p
     g=f         =       (a, b,   c2 )   = (c2 , −b, a) = (c, −b, ac).          (2.54)

      Определение. Форма вида (k, kn, c) называется неоднозначной (am-
biguous). Если форма – неоднозначна, то ее определитель делится на k :
D = (kn)2 − 4kc = k(kn2 − 4c).
      Идея метода Шенкса состоит в сопоставлении числу n, которое надо
разложить, квадратичной бинарной формы f с дискриминантом D = 4n, с
которой потом выполняется серия эквивалентных преобразований и переход
от формы f к неоднозначной форме (a0 , b0 , c0 ). Тогда, Н.О.Д.(a0 , b0 ) будет
являться делителем n. Более подробно алгоритм может быть записан в
следующем виде:

      Вход: Нечетное составное число n, которое требуется факторизовать.
Если n mod 4 = 1, заменим n на 2n. Теперь                          n mod 4 = 2 или 3.
Последнее свойство нужно, чтобы определитель квадратичной формы был
фундаментальным, что обеспечивает сходимость метода.
      Выход: Нетривиальный делитель n.

  1. Определим исходную квадратичную форму f = (1, 2b, b2 − D), с
                                     √
     дискриминантом D = 4n, где b = b nc.

  2. Выполним цикл редуцирований f = ρ(f ), пока форма f не станет
     квадратной:
     while not (f square ) do f = ρ(f );