On the Complexity of Computing Discrete Logarithms over Algebraic Tori
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.3 pp.442-447
- Publication Date
- 2014/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.442
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
- Category
- Fundamentals of Information Systems
Authors
Shuji ISOBE
Tohoku University
Eisuke KOIZUMI
Tohoku University
Yuji NISHIGAKI
Tohoku University
Hiroki SHIZUYA
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shuji ISOBE, Eisuke KOIZUMI, Yuji NISHIGAKI, Hiroki SHIZUYA, "On the Complexity of Computing Discrete Logarithms over Algebraic Tori" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 3, pp. 442-447, March 2014, doi: 10.1587/transinf.E97.D.442.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.442/_p
Copy
@ARTICLE{e97-d_3_442,
author={Shuji ISOBE, Eisuke KOIZUMI, Yuji NISHIGAKI, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Information},
title={On the Complexity of Computing Discrete Logarithms over Algebraic Tori},
year={2014},
volume={E97-D},
number={3},
pages={442-447},
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.},
keywords={},
doi={10.1587/transinf.E97.D.442},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - On the Complexity of Computing Discrete Logarithms over Algebraic Tori
T2 - IEICE TRANSACTIONS on Information
SP - 442
EP - 447
AU - Shuji ISOBE
AU - Eisuke KOIZUMI
AU - Yuji NISHIGAKI
AU - Hiroki SHIZUYA
PY - 2014
DO - 10.1587/transinf.E97.D.442
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2014
AB - 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.
ER -
English
