УДК 512.542
ОБ АЛЬТЕРНАТИВНЫХ СПОСОБАХ ЛОГАРИФМИРОВАНИЯ
В КОНЕЧНЫХ ГРУППАХ
Д.Е. Островский
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
Задача взятия дискретного логарифма сегодня известна, как одна из наиболее
вычислительно трудоемких. Не представлено ни одного алгоритма, способно-
го решать ее за полиномиальное время. Это одно из немногих вычислительно-
асимметричных преобразований, используемых в современной криптографии.
Выполнена попытка упростить решение задачи с целью оценить обоснован-
ность применения дискретного логарифма в асимметричных протоколах. Раз-
работан табличный алгоритм вычисления дискретного логарифма в произ-
вольной циклической группе порядка
n
, имеющий сложность
√
n
элементарных
операций. Математическое ожидание трудоемкости алгоритма составляет
√
n/
2
элементарных операций. Поэтому некоторые показатели вычисляются
быстрее остальных, причем они не обязательно по значению большие или ма-
ленькие, и анализ таких “небезопасных” показателей весьма затруднителен.
На практике алгоритм может оказаться эффективнее алгоритма согласо-
вания. Для группы
Zp
— умножения чисел по простому модулю путем син-
теза разработанного алгоритма с техникой факторных баз, применяемой в
алгоритме Адлемана, получен алгоритм, имеющий субэкспоненциальную слож-
ность
L
n
[1
/
2
,
√
3 ]
. В настоящее время известны более эффективные алго-
ритмы, тем не менее, показатель математического ожидания трудоемкости
может сыграть существенную роль на практике.
Ключевые слова
:
дискретный логарифм, циклические группы, группа
Zp
, ото-
бражение Ньютона, алгоритм Адлемана.
ON ALTERNATIVE WAYS OF TAKING THE LOGARITHM
IN FINITE GROUPS
D.E. Ostrovskii
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
A task of taking the discrete logarithm is known today as one of most computationally
complicated. There is no algorithm that can solve it in a polynomial time. This is one
of the few computationally asymmetric transformations used in modern cryptography.
An attempt is made here to simplify the problem solving, in order to assess the
reasonableness of using the discrete logarithm in asymmetric protocols. A tabular
algorithm for computing the discrete logarithm in an arbitrary cyclic group of
the order n is designed that has a complexity of
√
n
elementary operations. An
expectation of the algorithm complexity is
√
n/
2
elementary operations. Therefore
some indicators are computed faster than others, they are not necessarily large or
small in magnitude at that, and analysis of these “unsafe” indicators is rather hard.
In practice, this algorithm may be more efficient than the matching algorithm. For the
Zp
group (multiplication of numbers modulo a prime), by synthesizing the developed
algorithm with the technique of factor bases used in the Adleman’s algorithm, an
algorithm is obtained having a subexponential complexity of
L
n
[1
/
2
,
√
3
]. At the
present time, more efficient algorithms are known; nevertheless the indicator of
complexity expectation may play a significant role in the practice.
Keywords
:
discrete logarithm, cyclic groups,
Zp
group, Newton’s map, Adleman’s
algorithm.
80 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
