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).

Key words: finite fields, square root computation, Boolean complexity.

№ 5/2018