Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики / С. Б. Гашков, И. Б. Гашков. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2018. № 5. С. 8-14.
Доказано, что извлечь квадратный корень в поле 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).
