33-43

ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
В ПРОСТЫХ ПОЛЯХ И ПОЛЯХ ГАЛУА

Н. Б. Григорьев¹, А. Н. Леухин^2
1Поволжский государственный технологический университет,
Российская Федерация, 424000, Йошкар-Ола, пл. Ленина, 3
²Марийский государственный университет,
Российская Федерация, 424000, Йошкар-Ола, пл. Ленина, 1
E-mail: cydonia@list.ru

АННОТАЦИЯ

Представлены наиболее известные алгоритмы дискретного логарифмирования в конечных полях и полях Галуа. Они являются базовыми для многих современных алгоритмов. Многие из них были адаптированы для конкретных характеристик, с которыми до сих пор показывают хорошие вычислительные результаты.

КЛЮЧЕВЫЕ СЛОВА

дискретное логарифмирование; конечные поля; поля Галуа.

ПОЛНЫЙ ТЕКСТ (pdf)

СПИСОК ЛИТЕРАТУРЫ

1.    Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях. М.: Научный мир, 2004. 173 с.

2.    Pollard J. M. Monte Carlo methods for index computation (mod p) // Mathematics of Computation. 1978. Vol. 32. no 143 july 1978. pp 918-924.  DOI:10.1090/S0025-5718-1978-0491431-9.

3.    J. Pollard Kangaroos. Monopoly and Discrete Logarithms // Journal of Cryptology. 2000. Vol. 13. P. 437-447.

4.    Pohlig S., Hellman M. An improved algorithm for computing logarithms over and its cryptographic significance (Corresp.) // IEEE Transactions on Information Theory. 1978. January (volume 24, number 1). Pp. 106–110. DOI:10.1109/TIT.1978.1055817.

5.    Adleman L. A subexponential algorithm for the discrete logarithm problem with applications to cryptography // 20th Annual Symposium on Foundations of Computer Science.  1979.  October. Pp. 55–60. DOI:10.1109/SFCS.1979.2.

6.    Discrete logarithms in GF(p), D. Coppersmith, A. M. Odlyzko, and R. Schroeppel // Algorithmica. 1986. Vol. 1. Pp. 1-15.

7.    Coppersmith D. Fast evaluation of logarithms in fields of characteristic two // IEEE Transactions on Information Theory. 1984. Vol. 30, Iss. 4. Pp. 587–594. DOI:10.1109/TIT.1984.1056941.

8.    Hellman M. E. and Reyneri J. M. Fast computation of discrete logarithms in GF(q), Advances in Cryptography: Proceedings of CRYPTO '82 (D. Chaum, R. Rivest, A. Sherman, eds.), Plenum Press, New York, 1983. Pp. 3-13.

9.    Joux A. “A new index-calculus algorithm with complexity L(1/4+O(1)) in very small characteristic”, Selected Areas in Cryptography – SAC 2013, LNCS 8282. 2014, p. 355-379.

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

11.    Adleman L. M. and Huang M. A. Function field sieve method for discrete logarithms over finite fields // Information and Computation. 1999. Vol. 151, Pp. 5–16.

12.    Commeine A., Semaev I. An Algorithm to Solve the Discrete Logarithm Problem with the Number Field Sieve // Yung M., Dodis Y., Kiayias A., Malkin T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, Vol. 3958. Springer, Berlin, Heidelberg.

13.    Joux A., Lercier R. The Function Field Sieve in the Medium Prime Case. // Vaudenay S. (eds) Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, Vol. 4004. Springer, Berlin, Heidelberg.

14.    Joux A., Lercier R., Smart N., Vercauteren F. The Number Field Sieve in the Medium Prime Case // Dwork C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science. 2006. Vol 4117. Springer, Berlin, Heidelberg.

15.    Joux A., Odlyzko A., Pierrot C. The Past, Evolving Present and future of Discrete Logarithm // Ç.K. Koç (Ed.), Open Problems in Mathematics and Computational Science (pp. 5-36). Springer.

Для цитирования: Григорьев Н. Б., Леухин А. Н. Дискретное логарифмирование в простых полях и полях Галуа // Вестник Поволжского государственного технологического университета. Сер.: Радиотехнические и инфокоммуникационные системы. 2018. № 1 (37). С. 33-43. DOI: 10.15350/2306-2819.2018.1.33