Составители:
алгоритмов обратного преобразования Y → X является основным
критерием отнесения функции f к классу однонаправленных
функций.
Рассмотрим целочисленное умножение в качестве первого
примера однонаправленной функции. Прямой задачей является
вычисление произведения двух больших целых чисел P и Q, т.е.
нахождение значения
N = P Q . (3.3)
Обратной задачей является разложение на множители большого
целого числа, то есть определение делителей P и Q большого
целого числа N =P
⋅
Q, что является практически неразрешимой
задачей при достаточно больших значениях N. По современным
оценкам теории чисел при целом N ≈ 2
664
и P≈Q для разложения
числа N потребуется 10
23
операций, что для современных
вычислительных систем практически нереализуемо.
Модульная экспонента с фиксированными основанием и модулем
является следующим характерным примером однонаправленной
функции. Допустим, что a и N – целые числа такие, что 1≤ a < N.
Требуется определить множество Z
N
= ⎨0, 1, 2, …, N-1⎬.
Модульная экспонента с основанием a по модулю N представляет
собой функцию
f
a,N
(X) = a
X
(mod N), (3.4)
где X – целое число, 1≤ X ≤ N-1.
Задача вычисления значения функции f
a,N
(x) называется задачей
дискретного логарифмирования.
Сформулируем задачу дискретного логарифмирования
следующим образом. Для известных целых a, N, Y найти целое
число X такое, что
a
X
mod N = Y.
Модульная экспонента считается условно однонаправленной
функцией, так как алгоритм вычисления дискретного логарифма за
55
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
