论文标题
关于广义离散对数问题的复杂性
On the Complexity of Generalized Discrete Logarithm Problem
论文作者
论文摘要
广义离散对数问题（GDLP）是离散对数问题的扩展，其中的目标是在\ Mathbb {z} _s $ x中找到给定的$ g，y in \ mathbb {z} _s _s $的$ g^x \ mod s = y $。广义离散对数相似，但使用了许多基本元素，而不是单个基本元素，这些基础元素不一定彼此通勤。在本文中，我们证明了GDLP对于对称组是NP-HARD。此外，我们证明，即使基本元素是最多3个元素的排列，GDLP仍然是NP-HARD。最后，我们讨论了经典和量子复杂性理论中证明的含义和可能的含义。
Generalized Discrete Logarithm Problem (GDLP) is an extension of the Discrete Logarithm Problem where the goal is to find $x\in\mathbb{Z}_s$ such $g^x\mod s=y$ for a given $g,y\in\mathbb{Z}_s$. Generalized discrete logarithm is similar but instead of a single base element, uses a number of base elements which does not necessarily commute with each other. In this paper, we prove that GDLP is NP-hard for symmetric groups. Furthermore, we prove that GDLP remains NP-hard even when the base elements are permutations of at most 3 elements. Lastly, we discuss the implications and possible implications of our proofs in classical and quantum complexity theory.
