On the complexity of computing discrete logarithms over algebraic tori

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm problem over general finite fields (OCDL, in symbols) reduces to the discrete logarithm problem over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the prime factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm problem over general finite fields with respect to the Turing reducibility.

Original languageEnglish
Pages (from-to)442-447
Number of pages6
JournalIEICE Transactions on Information and Systems
VolumeE97-D
Issue number3
DOIs
Publication statusPublished - 2014

Keywords

  • Algebraic tori
  • Order certified discrete logarithm
  • Turing reduction

Fingerprint

Dive into the research topics of 'On the complexity of computing discrete logarithms over algebraic tori'. Together they form a unique fingerprint.

Cite this