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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.