Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic / S. B. Gashkov and I. B. Gashkov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2018. № 5. P. 8-14
[Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 176-181].
It was proved that the complexity of square root computation in the Galois field GF(3^s),s = 2^kr,
is equal to O(M(2^k)M(r)k + M(r)\log_2 r) + 2^k kr^{1+o(1)},
where M(n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3.
The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r))
and O(M(2^k)M(r))+ r^{1+o(1)}, respectively.
If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis,
then the summands 2^k kr^{1+o(1)} and r^{1+o(1)} can be omitted.
For M(n) one may take n \log_2 n \psi (n) , where \psi (n) grows slower than any iteration of the logarithm.
If k grows and r is fixed, than all the estimates presented here have the form O_r(M(s)\log_2 s) = s (\log_2 s)^2 \psi (s).
