This article is cited in 8 papers

On a connection between the complexities of the discrete logarithmization and the Diffie–Hellman problems

M. A. Cherepnev


Abstract: We prove that under some assumptions of a theoretical nature the complexity $L$ of the discrete logarithm problem in an arbitrary cyclic group of order $m$ is estimated in the rather general case in terms of the complexity $D$ of the Diffie–Hellman problem by the formula
$$ L \le \exp \left\{{\log D\log m\over \log\log m\log\log\log m}\right\}, $$
which gives a subexponential estimate for $L$ provided a polynomial estimate for $D$ is valid.

UDC: 519.624

Received: 22.05.1995

DOI: 10.4213/dm528

 English version: Discrete Mathematics and Applications, 1996, 6:4, 341–349

Bibliographic databases:

• 
•