On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism

Two-dimensional discrete logarithm problem in a finite additive group $G$ consists in solving the equation $Q=n_1P_1+n_2P_2$ with respect to $n_1$, $n_2$ for specified $P_1,P_2,Q\in G$, $0<N_1,N_2<\sqrt{|G|}$ such that there exists solution with $|n_1|\le N_1$, $|n_2|\le N_2$. In 2004, Gaudry and Schost proposed an algorithm to solve this problem with average complexity $(c+o(1))\sqrt N$ of group operations in $G$ where $c\approx2.43$, $N=4N_1N_2$, $N\to\infty$. In 2009, Galbraith and Ruprai improved this algorithm to obtain $c\approx2.36$. We show that the constant $c$ may be reduced if the group $G$ has an automorphism computable faster than the group operation.