pith. sign in

arxiv: 1310.7903 · v4 · pith:7BMLFCINnew · submitted 2013-10-29 · 💻 cs.CR · cs.CC· quant-ph

A reduction of semigroup DLP to classic DLP

classification 💻 cs.CR cs.CCquant-ph
keywords semigroupsgdlpalgorithmsclassicproblemreductionsamesubexponential
0
0 comments X
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.