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