Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики

Доказано, что извлечь квадратный корень в поле $GF(3^s),$ $s=2^kr,$ можно с битовой сложностью $O(M(2^k)M(r)k+M(r)\log_2 r)+2^k kr^{1+o(1)},$ где $M(n)$ – сложность умножения многочленов степени $n$ над полем характеристики $3.$ Умножение и деление в поле $GF(3^s)$ выполняются со сложностью $O(M(2^k)M(r))$ и $O(M(2^k)M(r))+r^{1+o(1)}$ соответственно. Если базис в поле $GF(3^r)$ определяется неприводимым биномом над $GF(3)$ или является оптимальным нормальным базисом, то слагаемые $2^k kr^{1+o(1)}$ и $r^{1+o(1)}$ можно опустить. В качестве $M(n)$ можно взять $n \log_2 n \psi(n) $, где $\psi(n)$ растет медленнее любой итерации логарифма. Если $k$ растет, а $r$ фиксировано, то все приведенные оценки имеют вид $O_r(M(s)\log_2 s)=s(\log_2 s)^2 \psi(s).$