Fast algorithm of square rooting in some odd characteгistic finite field

S. B. Gashkov ; I. B. Gashkov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2018), pp. 8-14

Résumé

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 with 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 binom 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).$