The discrete logarithm problem modulo a composite—abbreviate it as DLPC—is the following: given a (possibly) composite integer n ≥ 1 and elements $${a, b \in \mathbb{Z}_n^*}$$, determine an $${x \in \mathbb{N}}$$ satisfying a x  = b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem $${{\rm DLPC}_\varepsilon}$$ obtained by adding in the DLPC the constraint $${x\le (1-\varepsilon)n}$$, where $${\varepsilon}$$ is an arbitrary fixed number, $${0 < \varepsilon\le\frac{1}{2}}$$. We prove that factoring n reduces in deterministic subexponential time to the $${{\rm DLPC}_\varepsilon}$$ with $${O_\varepsilon((\ln n)^2)}$$ queries for moduli less or equal to n.
['Jacek Pomykała', 'Bartosz Źrałek']
On reducing factorization to the discrete logarithm problem modulo a composite