33-43

UDC 519.7
DOI: 10.15350/2306-2819.2018.1.33

DISCRETE LOGARITHM PROBLEM IN PRIME AND GALOIS FIELDS

N. B. Grigoriev¹, A. N. Leukhin²
¹Volga State University of Technology,
3, Lenin Square, Yoshkar-Ola, 424000, Russian Federation
²Mari State University,
1, Lenin Square, Yoshkar-Ola, 424000, Russian Federation
E-mail: cydonia@list.ru

ABSTRACT

Introduction. The discrete logarithm problem has not been solved yet. One of the reasons is that there are no efficient algorithms for solving it. Most modern algorithms are the improvement of classic algorithms of DLOG. The purpose of the work is to consider classical methods of the discrete logarithm, many of which were the basis of existing modern algorithms. Results. Algorithms and examples, describing them, are presented. The result of the work is the creation of the general table of algorithms, which shows the complexity of both classic and modern algorithms execution. Based on this table one can choose the most efficient algorithm for the work in a given field. Most algorithms work efficiently for the field of the certain characteristic.

KEYWORDS

DLP; discrete logarithm problem; finite fields; Galois fields

FULL TEXT (pdf)

REFERENCES

1. Ryabko B. Ya., Fionov A. N. Osnovy sovremennoy kriptografii dlya spetsialistov v informatsionnykh tekhnologiyakh [Fundamentals of Modern Cryptography for Information Technology Specialists]. Moscow: Nauchnyj mir, 2004. 173 p.
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 Dis-crete 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 Infor-mation 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 Founda-tions 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 compu-tation 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 character-istic”, Selected Areas in Cryptography – SAC 2013, LNCS 8282 (2014), p. 355-379.
10.   Matyukhin D. V. Ob asimptoticheskoy slozhnosti diskretnogo logarifmirovaniya v pole GF(p) [On the Asymptotic Complexity of the Discrete Logarithm in the Field GF (p)]. Diskretnaya matematika [Discrete Mathematics]. 2003. Vol. 15, Iss. 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 Num-ber Field Sieve. In: 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. In: Vaudenay S. (eds) Advances in Cryptology - EUROCRYPT 2006. EU-ROCRYPT 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. In: 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, In Ç.K. Koç (Ed.), Open Problems in Mathematics and Computational Science (pp. 5-36). Springer.

For citation: Grigoriev N. B., Leukhin A. N. Discrete Logarithm Problem in Prime and Galois Fields. Vestnik of Volga State University of Technology. Ser.: Radio Engineering and Infocommunication Systems. 2018. No 1 (37). Pp. 33-43. DOI: 10.15350/2306-2819.2018.1.33