Cryptology ePrint Archive: Report 2013/707
A reduction of semigroup DLP to classic DLP
Matan Banin and Boaz Tsaban
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.
Category / Keywords: foundations / discrete logarithm problem, quantum algorithms, semigroups.
Date: received 29 Oct 2013, last revised 31 Oct 2013
Contact author: tsaban at math biu ac il
Available format(s): PDF | BibTeX Citation
Note: Slightly better discussion of the (still open) nonperiodic case.
Version: 20131103:171919 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]