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

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

Цикл 1. Составим таблицу вычисления значений коэффициентов P , Q и r
по формулам (2.56). Вычисление заканчивается после того, как в столбце Q
появится полный квадрат:

       k   P    Q     r
       0   0    1    105
       1 105 86       2
       2   67   77    2
       3   87   46    4
       4   97   37    5
       5   88   91    2
       6   94   25    7
      В столбце Q найден полный квадрат d2 = 25, откуда находим значение
d = 5, используемое во втором цикле.

Цикл 2. Выполняем второй цикл вычислений. Цикл продолжается, пока в
столбце P 0 не появятся подряд два одинаковых значения. Тогда значение
Qj−1 , находящееся в предпоследней строке столбца Q, является искомым
делителем числа n.

       j   P0   Q0   r0
       0 -94    5    2
       1 104    59   3
       2   73   98   1
       3   25   107 1
       4   82   41   4
       5   82   107 1

      В столбце P были найдены два подряд идущих значения 82.
Завершаем вычисление. Предпоследнее значение в столбце Q содержит
искомый делитель 41 числа n = 11 111.
      Отметим, что теоретическое число итераций 2-ого цикла должно быть
примерно равно половине от числа итераций первого цикла (в нашем примере
j = 4 оказалось на единицу больше половины k = 6).