MarriageTheoremのこと

_ IACR ePrint 2013/720まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：A reduction of semigroup DLP to classic DLP, Matan Banin and Boaz Tsaban, http://eprint.iacr.org/2013/707

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.