# Algorithm for computing square roots in $GF(2^n)$

Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?

-

Yes, there is an algorithm for efficiently computing square roots in $GF(2^n)$.

I don't know if this is the most efficient known, but the existence of an efficient algorithm can be shown by observing that squaring within $GF(2^n)$ is a bitwise linear operation, hence it is equivalent to taking the bit representation of the value, and multiplying it by an $n\times n$ matrix in $GF(2)$ to obtain the bit representation of the sequence. Hence, it can be inverted by computing the inverse matrix, and multiplying by that.

Also, you have tagged the question with the "quadratic-residuosity" tag; however the field $GF(2^n)$ has the special property that all elements are quadratic residues; that is, for any element $x$, there will exist a unique element $y$ with $y^2 = x$. Hence, in this field, the quadratic residuosity question is uninteresting.

-
And that element $y$ will be simply $x^{2^{n-1}}$. ;) – fkraiem Jul 3 '14 at 20:04

To complete poncho's answer, if you know some Galois theory. The map $\sigma: x\mapsto x^2$ from $\mathbf{F}_{2^n}$ to itself is simply the Frobenius automorphism (relative to $\mathbf{F}_2$). It generates the Galois group $\mathrm{Gal}\left(\mathbf{F}_{2^n}/\mathbf{F}_2\right)$, which is cyclic of order $n$, and so its inverse (which is, by definition, the square root mapping) is $\sigma^{-1} = \sigma^{n-1} : x\mapsto x^{2^{n-1}}$.

Of course, you can simply notice that $$\left(x^{2^{n-1}}\right)^2 = x^{2\cdot 2^{n-1}} = x^{2^n} = x$$ (because in finite fields, the whole machinery of Galois theory boils down to repeated applications of the Frobenius automorphism, since it generates the Galois group).

-
Ah the Frobenius automorphism was the motivation, I should have seen that. I haven't touched field theory in a decade and I'm rusty :( – Arthur B Jul 3 '14 at 20:16

Nothing wrong with the other answers. I just want to point out that if you are using a normal basis representation of the field in question, then there is a very efficient way of calculating the square root. You recall that squaring of the element is equivalent to cyclically rotating its coordinates w.r.t. the normal basis. Therefore to calculate the square root you rotate in the opposite direction.

The use of normal bases is one of the more efficient ways of doing arithmetic in $GF(2^n)$ with $n>100$ or so.

-