On Alternative Ways of Taking the Logarithm in Finite Groups

A task of taking the discrete logarithm is known today as one of most computationally complicated. There is no algorithm that can solve it in a polynomial time. This is one of the few computationally asymmetric transformations used in modern cryptography. An attempt is made here to simplify the problem solving, in order to assess the reasonableness of using the discrete logarithm in asymmetric protocols. A tabular algorithm for computing the discrete logarithm in an arbitrary cyclic group of the order n is designed that has a complexity of √n elementary operations. An expectation of the algorithm complexity is √n/2 elementary operations. Therefore some indicators are computed faster than others, they are not necessarily large or small in magnitude at that, and analysis of these "unsafe" indicators is rather hard. In practice, this algorithm may be more efficient than the matching algorithm. For the Zp group (multiplication of numbers modulo a prime), by synthesizing the developed algorithm with the technique of factor bases used in the Adleman's algorithm, an algorithm is obtained having a subexponential complexity of L_n[1/2, √3]. At the present time, more efficient algorithms are known; nevertheless the indicator of complexity expectation may play a significant role in the practice.

References

[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, pp. 106-110.

[2] Shanks D. The infrastructure of a real quadratic field and its applications. Proc. Number Theory Conference. Un. of Colorado, Boulder, 1972. pp. 217-224.

[3] Glukhov M.M., Kruglov I.A., Pichkur A.B., Cheremushkin A.V. Vvedenie v teoretiko-chislovye metody kriptografii [Introduction to number-theoretic methods of cryptography]. SPb., Lan’ Publ., 2011. 400 p.

[4] Pollard J.M. Monte Carlo methods for index computation (mod p). Math. Comp., 1978, vol. 32, no. 143, pp. 918-924.

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

[6] Dixon J.D. Asymptotically fast factorization of integers. Math. Comp., 1981, vol. 36, no. 153, pp. 255-260.

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

[8] Vasilenko O.N. Teoretiko-chislovye algoritmy v kriptografii [Number-theoretic algorithms in cryptography]. Moscow, MTsNMO Publ., 2003. 328 p.

[9] Matyukhin D.V. On the asymptotic complexity of discrete taking the logarithm in the field GF(p) Diskretnaya matematika [Discrete Mathematics and Applications], 2003, vol. 15, iss. 1, pp. 28-49 (in Russ.).

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