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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 54
полученной таблицы:
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
k 28 28 14 14 14 7 28 14 28 28 4 14 28 28 7 4
Среди 28 значений a < 29 окажется 12 значение с показателем k = 28,
по 6 значений с показателем k = 14 и k = 7, 2 значения с k = 4, по одному с
k = 2 и k = 1. Математическое ожидание наименьшего показателя k равно:
M[k] = (12 · 28 + 6 · 14 + 6 · 7 + 2 ·4 + 2 ·1)/28 ≈ 16, 85
Таким образом, выбирая удачное a < n, можно получить значительный
выигрыш по сравнению с произвольным.
Дальнейшие улучшения алгоритма
Для ускорения всех вычислений Поллард предложил использовать
быстрое преобразование Фурье (a Fast Fourier Transform) для всех основных
операций.
Дальнейшие улучшения алгоритма были предложены П.Монтгомери
[30]. Он заметил, что на второй стадии алгоритма большую часть времени
отнимает вычисление для каждого простого числа q
i
из интервала [B
1
; B
2
]
Н.О.Д.(n, с
i
−1), где c
i
= b
q
i
. Монтгомери предложил объединять несколько
соседних элементов c
i
в блоки G
j
и вычислять сначала произведение h =
∏
(c
i
−1) mod n для всех c
i
∈ G
j
, а потом Н.О.Д.(n, h). Если Н.О.Д.(n, с
i
−
1) > 1, то таковым будет и Н.О.Д.(n, h ). Эти и другие улучшения, найденные
Монтгомери, позволяют в несколько раз сократить общее время работы
алгоритма.
На сайте www.loria.fr/∼zimmerma/records/Pminus1.html можно найти
таблицу рекордов разложения натуральных чисел, установленных с помощью
(p − 1)–метода Полларда.
Упражнение.
Сформируйте множество E
n
всех составных чисел n одинаковой
длины, являющихся произведением двух простых чисел. Найдите для
каждого числа n математическое ожидание M[k] наименьшего показателя
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                           54

полученной таблицы:
a   2     3     4   5    6   7   8   9   10 11 12 13 14 15 16 17
k 28 28 14 14 14 7 28 14 28 28                     4   14 28 28      7    4
        Среди 28 значений a < 29 окажется 12 значение с показателем k = 28,
по 6 значений с показателем k = 14 и k = 7, 2 значения с k = 4, по одному с
k = 2 и k = 1. Математическое ожидание наименьшего показателя k равно:

              M [k] = (12 · 28 + 6 · 14 + 6 · 7 + 2 · 4 + 2 · 1)/28 ≈ 16, 85

Таким образом, выбирая удачное a < n, можно получить значительный
выигрыш по сравнению с произвольным.

Дальнейшие улучшения алгоритма

        Для ускорения всех вычислений Поллард предложил использовать
быстрое преобразование Фурье (a Fast Fourier Transform) для всех основных
операций.
        Дальнейшие улучшения алгоритма были предложены П.Монтгомери
[30]. Он заметил, что на второй стадии алгоритма большую часть времени
отнимает вычисление для каждого простого числа qi из интервала [B1 ; B2 ]
Н.О.Д.(n, сi − 1), где ci = bqi . Монтгомери предложил объединять несколько
соседних элементов ci в блоки Gj и вычислять сначала произведение h =
∏
  (ci −1) mod n для всех ci ∈ Gj , а потом Н.О.Д.(n, h). Если Н.О.Д.(n, сi −
1) > 1, то таковым будет и Н.О.Д.(n, h). Эти и другие улучшения, найденные
Монтгомери, позволяют в несколько раз сократить общее время работы
алгоритма.
        На сайте www.loria.fr/∼zimmerma/records/Pminus1.html можно найти
таблицу рекордов разложения натуральных чисел, установленных с помощью
(p − 1)–метода Полларда.

Упражнение.

        Сформируйте множество En всех составных чисел n одинаковой
длины, являющихся произведением двух простых чисел. Найдите для
каждого числа n математическое ожидание M [k] наименьшего показателя

Страницы