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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 47
3.1. Метод Ферма
Пусть n = p·q – нечетное целое число, являющееся произведением двух
неизвестных простых чисел p и q , которые требуется найти. Большинство
современных методов факторизации основано на идее, предложенной еще
Пьером Ферма, заключающейся в поиске пар натуральных чисел A и B таких,
что выполняется соотношение:
n = A
2
− B
2
. (3.20)
Алгоритм Ферма может быть описан следующим образом:
1. Вычислим целую часть от квадратного корня из n:
x
0
= ⌈
√
n⌉.
2. Для x
i
= x
0
+ i, i = 0, 1, 2, ... будем вычислять значения
q(x
i
) = x
2
i
− n, (3.21)
до тех пор, пока очередное значение q(x
i
) не окажется равным полному
квадрату.
3. Пусть q(x
i
) является полным квадратом, например, числа B :
q(x
i
) = B
2
. Определим A = x
i
, откуда из равенства A
2
− n = B
2
найдем
n = A
2
− B
2
= (A + B) · (A − B), и искомые делители p и q вычисляются,
как p = A + B , q = A − B .
Пример. Пусть факторизуемое число n = 19 691. Вычислим m =
⌈
√
n⌉ = 141. Представим процедуру вычисления делителей n в виде
таблицы:
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                     47

3.1. Метод Ферма
     Пусть n = p·q – нечетное целое число, являющееся произведением двух
неизвестных простых чисел p и q , которые требуется найти. Большинство
современных методов факторизации основано на идее, предложенной еще
Пьером Ферма, заключающейся в поиске пар натуральных чисел A и B таких,
что выполняется соотношение:

             n = A2 − B 2 .                                           (3.20)

      Алгоритм Ферма может быть описан следующим образом:

      1. Вычислим целую часть от квадратного корня из n:
                  √
            x0 = ⌈ n⌉.


      2. Для xi = x0 + i, i = 0, 1, 2, ... будем вычислять значения

              q(xi ) = x2i − n,                                       (3.21)

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

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

      Пример. Пусть факторизуемое число n = 19 691. Вычислим m =
√
⌈ n⌉ = 141. Представим процедуру вычисления делителей n в виде
таблицы:

Страницы