Index-calculus algorithm for calculating the discrete logarithms based on index tables
DOI:
https://doi.org/10.15276/opu.1.43.2014.30Keywords:
encryption, index-calculus, discrete logarithm, p-smooth numberAbstract
The complexity of the discrete logarithm problem is the basis of many asymmetric encryption algorithms cryptographic sta-bility, such as the widely used cryptographic algorithm RSA. One of the most effective algorithm to compute discrete loga-rithms is the index-calculus algorithm, however, its computational complexity is high. The purpose is to improve the algo-rithm for calculation of discrete logarithms based on the use of index tables, which are used in many areas of modern com-munication theory and cryptography. It is found that the use of index tables can greatly simplify the problem of discrete loga-rithms computing, which makes possible the development of new encryption algorithms with practically attractive properties. It is also valuable from the standpoint of cryptanalysis of the existing cryptographic algorithms based on the computational complexity of the discrete logarithm problem. Keywords: encryption, index-calculus, discrete logarithm, p-smooth number
Downloads
References
Рябко, Б.Я. Основы современной криптографии и стеганографии / Б.Я. Рябко, А.Н. Фионов. - М.: Горячая линия - Телеком, 2010. - 232 с.
Ишмухаметов, Ш.Т. Методы факторизации натуральных чисел / Ш.Т. Ишмухаметов. - Казань: Казан. ун. КФУ, 2011. - 190 с.
Вялый, М. Квантовые компьютеры и квантовые вычисления [Электронный ресурс] / М. Вялый // Кафедра информатики МФТИ. - Режим доступа: http://cs.mipt.ru/docs/comp/rus/develop/ other/quantum_comp (Дата обращения: 26.11.2013).
Buchmann, J. On some computational problems in finite abelian groups / J. Buchmann, M.J. Jacobson, Jr., E. Teske. - Mathematics of Computation. - 1997. - Vol. 66, No. 220. - PP. 1663 - 1687.
Studholme, C. The Discrete Log Problem [Электронный ресурс] / C. Studholme // Department of Computer Science, University of Toronto. - 2002. - 57 p. - Режим доступа: http://www.cs.toronto. edu/~cvs/dlog/research_paper.pdf (Дата обращения: 26.11.2013).
Виноградов, И.М. Основы теории чисел / И.М. Виноградов. - М.: Регулярная и хаотическая ди-намика, 2003. - 176 с.
Мазурков, М.И. Системы широкополосной радиосвязи / М.И. Мазурков. ― Одесса.: Наука и техника, 2010. ― 340 с.8.Варакин, Л.Е. Системы связи с шумоподобными сигналами: монография / Л.Е. Варакин. ― М.: Радио и связь, 1985. ― 384 с.
