(Short Paper) How to Solve DLOG Problem with Auxiliary Input

Let \(\mathbb {G}\) be a group of prime order p with a generator g. We first show that if \(p-1=d_1 \ldots d_t\) and \(g,g^x\), \( g^{x^{(p-1)/d_1}}, \ldots , \ g^{x^{(p-1)/(d_1 \ldots d_{t-1})}}\) are given, then x can be computed in time \( O(\sqrt{d_1}+ \ldots + \sqrt{d_t} ) \) exponentiations. Further suppose that \(p-1=d_1^{e_1} \ldots d_t^{e_t}\), where \(d_1, \ldots , d_t\) are relatively prime. We then show that x can be computed in time \( O(e_1\sqrt{d_1}+\ldots + e_t\sqrt{d_t}) \) exponentiations if g and \( g^{x^{(p-1)/d_i}}, \ldots , g^{x^{(p-1)/d_i^{e_i-1}}} \) are given for \(i=1, \ldots , t\).