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

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

факторизации, являясь самым чемпионом для чисел от 1010 до 1018 .
Кроме того, этот метод используется как вспомогательный при разложении
делителей больших чисел типа чисел Ферма.

       Определение. Бинарной квадратичной формой называется полином
от двух переменных x и y :
                                            !       !
                                      a b       x
f (x, y) = ax2 + bxy + cy 2 = (x y)                     .
                                      0 c       y

       Будем записывать квадратичную форму f = ax2 + bxy + cy 2 в более
кратком виде f = (a, b, c). Дискриминантом формы (a, b, c) называется
число D = b2 − 4ac. Формы с отрицательным дискриминантом называются
определенными – definite, а формы с положительным дискриминантом
неопределенными – indefinite. В методе Шенкса используются только
неопределенные формы.

       Определение. Две квадратичные формы f = (a, b, c) и g = (p, q, r)
называются эквивалентными, если найдется целочисленная матрица
                        !
                    α β
                        γ δ
с определителем равным 1, переводящая матрицу f в матрицу g :
              !          !         !        !
          p q       α γ        a b      α β
                =           ·        ·
          0 r       β δ        0 c      γ δ
       Поскольку эквивалентное преобразование не меняет детерминант
формы, необходимым условием эквивалентности двух форм является
равенства    их    детерминантов.     Однако,       обратное   неверно.   Среди
форм с одинаковым дискриминантом может найтись конечное число
неэквивалентных.
       Среди класса всех квадратичных форм, эквивалентных данной, имеют
особое значение так называемые редуцированные формы. Форма f = (a, b, c)
называется редуцированной, если выполняется неравенство
      √               √
     | D − 2|a|| < b < D.                                                 (2.49)