A reduction of semigroup DLP to classic DLP
This work addresses a theoretical problem in cryptography and computational algebra, offering incremental progress by extending known results from groups to semigroups.
The authors tackled the discrete logarithm problem in periodic semigroups by providing a polynomial-time reduction to the classic discrete logarithm problem in subgroups, enabling quantum computers to solve it in polynomial time and allowing subexponential algorithms when available for the corresponding groups.
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.