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

Глава 2. Криптостойкость RSA. Алгоритмы факторизации                  59

      Отметим, что в некоторых случаях, последовательность {yn } может
зацикливаться (т.е. на некотором шаге t появляется xt = x0 , после чего
последовательность повторяется), тогда надо поменять исходный элемент x0
или полином F (x) на какой–нибудь другой.

Упражнения.

  1. Подберите несколько составных чисел n одинаковой длины, и
     выполните пробное разложение этих чисел методом Полларда.
     Вычислите среднее время (количество итераций) до нахождения
     нетривиального делителя n. Как сильно отличается время вычисления
     для различных n?

  2. Выполните упражнение 1 с алгоритмом Флойда. Сравните среднее
     время вычисления делителя в первом и втором случаях.


3.5. ρ-метод Полларда для вычисления дискретного
     логарифма
     Проблема дискретного логарифма (Discrete Logarithm Problem DLP)
состоит в вычислении в конечном поле Fq с образующей g для произвольного
элемента t наименьшего числа k такого, что g k = t. Хотя эта проблема не
связана непосредственно с проблемой факторизации целых чисел, она играет
важную роль в криптографии. При длине ключа L проблема DLP имеет
такую же сложность решения, как и проблема факторизации числа длины L,
поэтому на проблеме вычисления DLP построено много криптографических
протоколов, в том числе, известные протоколы Диффи-Хелмана вычисления
общего секретного ключа и Эль-Гамаля электронной цифровой подписи.
      Существует большое число различных методов для решения этой
задачи. В главе 5 книги Л.Вашингтона [36] дано описание основных
алгоритмов для ДЛЭК. В этом разделе мы рассмотрим ρ-метод Полларда
для DLP, который играет здесь ту же роль, что и ρ-метод Полларда для
проблемы факторизации. Группу по умножению поля Fp , p–простое число,
обозначим через Fp∗ = {1, 2 ... p − 1}. Напомним, что элемент g ∈ Fp∗