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

Рассматривается двумерная задача дискретного логарифмирования для подгруппы $G$ группы точек эллиптической кривой над конечным простым полем, обладающей эффективным автоморфизмом порядка 6 (для заданных $P_1,P_2,Q \in G$, ${0<N_1,N_2<\sqrt{|G|}}$ требуется найти такие $n_1,n_2$, что $Q=n_1P_1+n_2P_2,~{-N_1\leq n_1 \leq N_1}, ~{-N_2\leq n_2 \leq N_2}$). Для этой задачи конструктивно доказывается, что для любого ${\varepsilon>0}$ существует модификация алгоритма Годри–Шоста, средняя трудоемкость которой не превосходит ${(1+\varepsilon)0.847\sqrt{N} + O _{\varepsilon} (N ^ {1/4})}$ групповых операций при $N=4N_1N_2, ~N\to \infty$.