A reduction of semigroup DLP to classic DLP
classification
💻 cs.CR
cs.CCquant-ph
keywords
semigroupsgdlpalgorithmsclassicproblemreductionsamesubexponential
read the original abstract
We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion) semigroup (SGDLP) to the same problem in a subgroup of the same semigroup. It follows that SGDLP can be solved in polynomial time by quantum computers, and that SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.