Теория электрической связи. Васильев К.К - 415 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

415
В качестве примера однонаправленной функции
()
xfy
=
рассмотрим ши-
роко известную функцию дискретного возведения в степень:
()
py
x
mod
α
= , где
x
– целое число от 1 до 1−p включительно, а вычисление производится по мо-
дулю
p
, где
p
– очень большое простое число;
α
– целое число ( p<<
α
1 ).
Напомним, что простым числом называется целое число, которое не де-
лится ни на какие числа, кроме себя самого и единицы.
Пример 10.1. Для примера возьмем небольшое простое число
7=p ; тогда
для осуществления преобразований можно выбрать примитивный элемент
3=
α
, так как
()
37mod
1
=
α
,
(
)
(
)
(
)
27mod97mod37mod
22
===
α
,
()
67mod
3
=
α
,
()
47mod
4
=
α
,
()
57mod
5
=
α
,
()
17mod
6
=
α
.
Функция
()
py
x
mod
α
= вычисляется сравнительно просто, а обратная к ней
функция
px
y
log= является вычислительно сложной практически для всех
(
py <<1 ) при условии, что не только
p
велико, но и ( 1
−
p ) имеет большой про-
стой множитель (лучше всего, если это будет другое простое число, умножен-
ное на 2). В связи с этим такую задачу называют задачей нахождения дискрет-
ного логарифма или задачей дискретного логарифмирования.
Задача дискретного логарифмирования состоит в том, что для известных
целых
α
,
p
, y необходимо найти целое число
x
. Однако алгоритм вычисления
дискретного логарифма за приемлемое время пока не найден. Поэтому модуль-
ная экспонента считается однонаправленной функцией.
По современным оценкам теории чисел при целых числах
664
2≈
α
и
664
2≈p решение задачи дискретного логарифмирования потребует около
26
10
операций, что имеет в
3
10 раз большую вычислительную сложность, чем задача
разложения на множители. При увеличении длины чисел разница в оценках
сложности задач возрастает.
Следует отметить, что пока не удалось доказать, что не существует эф-
фективного алгоритма вычисления дискретного логарифма за приемлемое вре-
мя. Исходя из этого, модульная экспонента отнесена к однонаправленным
функциям условно, что,
однако, не мешает с успехом применять ее на практике.

Страницы