On the Complexity of Computing Discrete Logarithms over Algebraic Tori

• ISOBE Shuji

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University

• KOIZUMI Eisuke

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University

• NISHIGAKI Yuji

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University

• SHIZUYA Hiroki

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E97.D (3), 442-447, 2014

  The Institute of Electronics, Information and Communication Engineers

Keywords

• algebraic tori
• order certified discrete logarithm
• Turing reduction

Details

• CRID: 1390282679354364288
• NII Article ID: 130003394859
• DOI: 10.1587/transinf.e97.d.442
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E97.D/3/E97.D_442/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed