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

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

      2. Для x = 1, 2, ... будем вычислять значения

            q(x) = (m + x)2 − n,                                   (2.21)

до тех пор, пока очередное значение q(x) не окажется равным полному
квадрату.

      3. Пусть q(x) является полным квадратом, например, числа B : q(x) =
B 2 . Определим A = m + x, откуда из равенства A2 − n = B 2 найдем n =
A2 − B 2 = (A + B) · (A − B), и искомые делители p и q вычисляются, как
p = A + B, q = A − B.

      Пример. Пусть факторизуемое число n = 19 691. Вычислим m =
√
b nc = 140. Представим процедуру вычисления делителей n в виде
таблицы:
                  √
       x     y        y
       1    190   13,78
       2    473   21,75
       3    758   27,53
       4    1045 32,33
       5    1334 36,52
       6    1625 40,31
       7    1918 43,79
       8    2213 47,04
       9    2510 50,10
       10 2809     53

      Из последнего столбца получим: (140 + 10)2 − n = 532 , откуда n =
1502 − 532 = 203 · 97. Итак, 19 691 = 203 · 97, и вычисление потребовало
10 итераций, в каждой из которых было выполнено 1 возведение в степень,
1 вычитание и одно вычисление квадратного корня, т.е. константное число
операций.

      Оценка производительности метода Ферма