Welcome to the resource topic for 2013/707
Title:
A reduction of Semigroup DLP to classic DLP
Authors: Matan Banin, Boaz Tsaban
Abstract:We present a polynomial-time reduction of the discrete logarithm problem in any periodic (or torsion) semigroup (SGDLP) to the classic DLP 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 complexity whenever the classic DLP in the corresponding groups has subexponential complexity. We also consider several natural constructions of nonperiodic semigroups, and provide polynomial time solutions for the DLP in these semigroups.
ePrint: https://eprint.iacr.org/2013/707
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .