You are looking at a specific version 20131103:171919 of this paper.
See the latest version.
Paper 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.
Note: Slightly better discussion of the (still open) nonperiodic case.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- discrete logarithm problemquantum algorithmssemigroups.
- Contact author(s)
- tsaban @ math biu ac il
- History
- 2015-11-02: last of 2 revisions
- 2013-11-03: received
- See all versions
- Short URL
- https://ia.cr/2013/707
- License
-
CC BY