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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 65
2.5. ρ-метод Полларда для вычисления дискретного
логарифма
Проблема дискретного логарифма (Discrete Logarithm Problem DLP)
состоит в вычислении в конечном поле F
q
с образующей g для произвольного
элемента t наименьшего числа k такого, что g
k
= t. Хотя эта проблема не
связана непосредственно с проблемой факторизации целых чисел, она играет
важную роль в криптографии. При длине ключа L проблема DLP имеет
такую же сложность решения, как и проблема факторизации числа длины L,
поэтому на проблеме вычисления DLP построено много криптографических
протоколов, в том числе, известные протоколы Диффи-Хелмана вычисления
общего секретного ключа и Эль-Гамаля электронной цифровой подписи.
Существует большое число различных методов для решения этой
задачи. В главе 5 книги Л.Вашингтона [54] дано описание основных
алгоритмов для ДЛЭК. В этом разделе мы рассмотрим ρ-метод Полларда
для DLP, который играет здесь ту же роль, что и ρ-метод Полларда для
проблемы факторизации. Группу по умножению поля F
p
, p–простое число,
обозначим через F
∗
p
= {1, 2 ... p − 1}. Напомним, что элемент g ∈ F
∗
p
называется генератором поля, если любой элемент t ∈ F
∗
p
равен некоторой
степени элемента g : t = g
k
. Пусть g – (какой-нибудь) генератор этой группы,
и пусть t - произвольный элемент F
∗
p
.
Для нахождения неизвестного показателя k такого, что g
k
= t,
будем строить последовательность пар (a
i
, b
i
) чисел по модулю p − 1 и
последовательность x
i
чисел по модулю p такую что x
i
= t
a
i
g
b
i
. Определим
начальные значения a
0
= b
0
= 0, x
0
= 1. Вычисление последующих членов
последовательностей будем выполнять по формулам:
(a
i+1
, b
i+1
) =
(a
i
+ 1, b
i
) mod (p −1), если 0 < x
i
< p/3,
(2a
i
, 2b
i
) mod (p − 1), если p/3 < x
i
< 2p/3,
(a
i
, b
i
+ 1) mod (p − 1) если 2p/3 < x
i
< p,
(2.27)
Глава 2. Простые алгоритмы факторизации                                     65

2.5. ρ-метод Полларда для вычисления дискретного
      логарифма
      Проблема дискретного логарифма (Discrete Logarithm Problem DLP)
состоит в вычислении в конечном поле Fq с образующей g для произвольного
элемента t наименьшего числа k такого, что g k = t. Хотя эта проблема не
связана непосредственно с проблемой факторизации целых чисел, она играет
важную роль в криптографии. При длине ключа L проблема DLP имеет
такую же сложность решения, как и проблема факторизации числа длины L,
поэтому на проблеме вычисления DLP построено много криптографических
протоколов, в том числе, известные протоколы Диффи-Хелмана вычисления
общего секретного ключа и Эль-Гамаля электронной цифровой подписи.
      Существует большое число различных методов для решения этой
задачи. В главе 5 книги Л.Вашингтона [54] дано описание основных
алгоритмов для ДЛЭК. В этом разделе мы рассмотрим ρ-метод Полларда
для DLP, который играет здесь ту же роль, что и ρ-метод Полларда для
проблемы факторизации. Группу по умножению поля Fp , p–простое число,
обозначим через Fp∗ = {1, 2 ... p − 1}. Напомним, что элемент g ∈ Fp∗
называется генератором поля, если любой элемент t ∈ Fp∗ равен некоторой
степени элемента g : t = g k . Пусть g – (какой-нибудь) генератор этой группы,
и пусть t - произвольный элемент Fp∗ .
      Для нахождения неизвестного показателя k такого, что g k = t,
будем строить последовательность пар (ai , bi ) чисел по модулю p − 1 и
последовательность xi чисел по модулю p такую что xi = tai g bi . Определим
начальные значения a0 = b0 = 0, x0 = 1. Вычисление последующих членов
последовательностей будем выполнять по формулам:
                    
                     (ai + 1, bi ) mod (p − 1), если 0 < xi < p/3,
                    
                    
   (ai+1 , bi+1 ) =   (2ai , 2bi ) mod (p − 1),  если p/3 < xi < 2p/3,   (2.27)
                    
                     (ai , bi + 1) mod (p − 1)
                    
                                                 если 2p/3 < xi < p,

Страницы