О сложности двумерной задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом порядка 6

Двумерная задача дискретного логарифмирования в конечной группе $G$ (с аддитивной записью операции) заключается в поиске для заданных $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$, в предположении, что эти значения существуют. В 2004 году Годри и Шост предложили алгоритм решения этой задачи, средняя трудоемкость которого при стандартных эвристических предположениях равна $(c+o(1))\sqrt N$ групповых операций в $G$, где $c\approx2.43$, $N=4N_1N_2$, $o(1)\to0$ при $N\to\infty$. В 2009 году Гэлбрэйт и Рупраи усовершенствовали алгоритм Годри–Шоста, получив $c\approx2.36$.
В настоящей работе показано, что для группы точек эллиптической кривой над конечным простым полем, имеющей эффективный автоморфизм $\varphi$ порядка 6, средняя трудоемкость алгоритма Годри–Шоста решения двумерной задачи дискретного логарифмирования при $P_2=\varphi(P_1)$ и $N_1=N_2$ не превосходит $(c+o(1))\sqrt N$, где $c\approx0.9781$.