On the Complexity of the Discrete Logarithm for a General Finite Group

Tatsuaki OKAMOTO  Kouichi SAKURAI  Hiroki SHIZUYA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.1   pp.61-65
Publication Date: 1996/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
discrete logarithm,  computational complexity,  cryptography,  

Full Text: PDF(504.7KB)>>
Buy this Article

GDL is the language whose membership problerm is polynomial-time Turing equivalent to the discrete logarithm problem for a general finite group G. This paper gives a characterization of GDL from the viewpoint of computational complexity theory. It is shown that GDL NP co-AM, assuming that G is in NP co-NP, and that the group law operation of G can be executed in polynomial time of the element size. Furthermore, as a natural probabilistic extension, the complexity of GDL is investigated under the assumption that the group law operation is executed in an expected polynomial time of the element size. In this case, it is shown that GDL MA co-AM if G MA co-MA. As a consequence, we show that GDL is not NP-complete unless the polynomial time hierarchy collapses to the second level.