Modified Gaudry–Schost algorithm for the two-dimensional discrete logarithm problem

We consider the two-dimensional discrete logarithm problem for the subgroup $G$ of a rational points group of an elliptic curve defined over a finite prime field that has an efficient automorphism of order 6 (for given $P_1, P_2, Q \in G, 0 <N_1, N_2 < \sqrt {| G |}$ we have to find $n_1, n_2$ such that $Q = n_1P_1 + n_2P_2, ~-N_1 \leq n_1 \leq N_1, -N_2 \leq n_2 \leq N_2$). For this problem, modification of the Gaudry–Schost algorithm is suggested such that for any ${\varepsilon>0}$ there exists an algorithm with average complexity not exceeding ${(1+ \varepsilon) 0.847\sqrt {N} + O _{\varepsilon} (N ^ {1/4}) }$ group operations for ${ N = 4N_1N_2, ~N \to \infty }$.