Эффективный вариант метода решета числового поля для дискретного логарифмирования в поле $\mathbf{GF}(p^k)$

В работе изложен алгоритм дискретного логарифмирования в мультипликативной группе поля $\mathbf{GF}(p^k)$, где $p$ – большое простое число, $k$ – фиксировано, являющийся вариантом метода решета числового поля. При некоторых эвристических предположениях доказано, что сложность алгоритма по порядку не превышает
$$ \exp\{[(64/9)^{1/3}+o(1)](\ln p^k)^{1/3}(\ln\ln p^k)^{2/3}\} $$
двоичных операций, где $o(1)\to0$ при $p\to\infty$, что совпадает с аналогичной оценкой для варианта метода, предложенного О. Широкауэром. Алгоритм, предложенный в настоящей работе, представляется более простым и эффективным с точки зрения практической реализации.