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

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

k   P      Q     r     p      q       p2 − nq 2
0    0     1    105   105     1         -86
1 105 86         2    211     2          77
2   67     77    2    1527    5         -46
3   87     46    4    2319   22          37
4   97     37    5    12122 115         -91
5   88     91    2    26563 252          25

         Значение выражения p2 − nq 2 в последней строке стало равно
полному квадрату 25, откуда 252n = 265632 − 52 . Вычисляя с помощью
алгоритма Евклида d=Н.О.Д(n, 26563 + 5) =Н.О.Д(26568, 11111), найдем
нетривиальный делитель d = 41 числа n.

      Заметим, что наша таблица позволяет также вычислить значение
                                                               √
квадратного корня из n = 11 111. Действительно, точное значение 11 111 =
105, 408 728 3..., а последняя подходящая дробь дает отношение p5 /q5 =
105, 408 730 1, которое отличается от точного меньше, чем на 2 · 10−6 .
      Замечание. Отметим здесь, что сами авторы метода CFRAC строили
                                                   √
последовательность дробей, сходящуюся к корню        n, итерационным
методом     Ньютона.       Лишь       позже   было   замечено,   что   использовать
непрерывные дроби удобнее. В 4-ой главе мы рассмотрим использование
непрерывных дробей в методе квадратичного решета.


2.8. Факторизация                 с     использованием           квадратичных
      форм
      Метод факторизации, основанный на квадратичных бинарных формах,
получил название SQUFOF от английского SQUare FOrm Factorization и
был разработан в 1975 г. Даниелем Шенксом (D. Shanks), хотя сам Шенкс
не опубликовал ни одной статьи, посвященной этому методу. Подробнее об
истории этого метода и о его связи с методом непрерывных дробей можно
узнать из статьи Говера и Вагстаффа (J. Gover, S.S. Wagstaff [25]).
         Этот метод занимает свою нишу в классификации различных методов