Личный кабинет
Подробное описание документа
Островский Д. Е.
Об альтернативных способах логарифмирования в конечных группах / Островский Д. Е. // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. - 2014. - № 2. -
Задача взятия дискретного логарифма сегодня известна, как одна из наиболее вычислительно трудоемких. Не представлено ни одного алгоритма, способного решать ее за полиномиальное время. Это одно из немногих вычислительноасимметричных преобразований, используемых в современной криптографии. Выполнена попытка упростить решение задачи с целью оценить обоснованность применения дискретного логарифма в асимметричных протоколах. Разработан табличный алгоритм вычисления дискретного логарифма в произвольной циклической группе порядка n, имеющий сложность √n элементарных операций. Математическое ожидание трудоемкости алгоритма составляет √n/2 элементарных операций. Поэтому некоторые показатели вычисляются быстрее остальных, причем они не обязательно по значению большие или маленькие, и анализ таких "небезопасных" показателей весьма затруднителен. На практике алгоритм может оказаться эффективнее алгоритма согласования. Для группы Zp - умножения чисел по простому модулю путем синтеза разработанного алгоритма с техникой факторных баз, применяемой в алгоритме Адлемана, получен алгоритм, имеющий субэкспоненциальную сложность Ln[1/2, √3]. В настоящее время известны более эффективные алгоритмы, тем не менее, показатель математического ожидания трудоемкости может сыграть существенную роль на практике.
