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

Глава 2. Криптостойкость RSA. Алгоритмы факторизации                  48
                    √
        x    q(x)    q(x)
       141   190    13,78
       142   473    21,75
       143   758    27,53
       144 1045     32,33
       145 1334     36,52
       146 1625     40,31
       147 1918     43,79
       148 2213     47,04
       149 2510     50,10
       150 2809      53

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

      Оценка производительности метода Ферма
В наихудшем случае, когда q близко к 1, а p близко к n, алгоритм будет
работать даже хуже, чем метод пробных делений. Действительно, A = (p +
q)/2, откуда число итераций в методе Ферма равно
                                p+q            n
                    Iter(n) =       − ⌊n1/2 ⌋ ≈ − ⌊n1/2 ⌋,
                                 2             2
т.е. имеет порядок 0(n). Для того, чтобы метод Ферма работал не хуже, чем
метод пробных делений необходимо, чтобы Iter(n) было меньше n1/2 , откуда
больший делитель p < 4n1/2 .
      Таким образом, как и метод пробного деления, алгоритм Ферма имеет
экспоненциальную оценку и не эффективен для разложения длинных чисел.
      Можно улучшить метод Ферма, выполнив сначала пробное деление
числа n на числа от 2 до некоторой константы B , исключив тем самым
малые делители n до B включительно, и только потом выполнить поиск