Об альтернативных способах логарифмирования в конечных группах

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

Литература

[1] Pohlig S.C., Hellman M.E. An Improved Algorithm for Computing Logarithms Over GF(p) and its Cryptographic Significance // IEEE, Transactions on Information Theory. 1978. Vol. 1. No. 24. P. 106-110.

[2] Shanks D. The infrastructure of a real quadratic field and its applications // Proceedings of the Number Theory Conference. University of Colorado, Boulder. 1972. P. 217-224.

[3] Глухов М.М., Круглов И.А., Пичкур А.Б., Черемушкин А.В. Введение в теоретикочисловые методы криптографии. СПб.: Лань, 2011. 400 с.

[4] Pollard J.M. Monte Carlo methods for index computation (mod p) // Math. Comp. 1978. No. 32. P. 918-924.

[5] Adleman L.M. A subexponentional algorithm for the discrete logarithm problem with applications to cryptography. Proceedings of the IEEE 20th Annual Symposium on Foundations of Computer Science. 1979. P. 55-60.

[6] Dixon J.D. Asymptotically fast factorization of integers // Math. Comp. 36 (153). 1981. P. 255-260.

[7] De Bruijn N.G., Erdos P. A combinatioral [sic] problem // Indagationes Mathematica. Vol. 10. 1948. P. 421-423.

[8] Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО. 2003. 328 с.

[9] Матюхин Д.В. Об асимптотической сложности дискретного логарифмирования в поле GF(p) // Дискретная математика. 2003. Т. 15. Вып. 1. С. 28-49.

[10] Coppersmith D., Odlyzko A.M., Schroeppel R. Discrete logarithms in GF(p). Algorithmica. 1986. Vol. 1. P. 1-15.