Square root for Galois fields $GF(2^m)$

Solution 1:

As egreg's answer points out, every element of $GF(2^m)$ has a square root. However, computing the square root is much easier than might be inferred from the last sentence in that answer.

The square root of $x \in GF(2^m)$ is $\sqrt{x} = x^{2^{m-1}} = ((\cdots((x^2)^2)^2\cdots )^2$. If the elements of $GF(2^m)$ are represented as $m$-bit (row) vectors $\mathbf x = (x_0, x_1, \ldots, x_{m-1})$ with respect to some basis, then $\sqrt{x}$ has representation $\mathbf xA$ with respect to the same basis where $A$ is a $m\times m$ matrix over $GF(2)$. As a special case, if the basis happens to be a normal basis, then the square root of $x$ has representation $(x_1, \ldots, x_{m-1}, x_0)$ with respect to the normal basis.

Solution 2:

If $G$ is an abelian group, the map $s:G\to G$ defined by $s(x)=x^2$ is a homomorphism. The kernel of $s$ is $$ \ker s=\{x\in G: x^2=1\} $$ so it consists of the elements having order $1$ or $2$. But if the group is finite with odd order, it can't have elements of order $2$ because of Lagrange's theorem. Thus we conclude that

If $G$ is a finite abelian group of odd order, then the map $x\mapsto x^2$ is an automorphism (bijective homomorphism $G\to G$).

This is the case of $GF(2^m)^*$, the multiplicative group of non zero elements of $GF(2^m)$ that has odd order $2^m-1$.

Since $0$ obviously has a square root, we conclude that the square root function is well defined on the whole $GF(2^m)$.

It's indeed true that $GF(2^m)^*$ is cyclic, so there exists an element $a\in GF(2^m)$ such that every element of $GF(2^m)^*$ is of the form $a^k$. Once this element is found, the square root can, in principle, be computed.

Solution 3:

For the field $GF(p^m)$ the map $$F: x\mapsto x^p$$ is an automorphism of order $m$, that is $$F^m(x) =x^{p^m} = x$$ and so the the inverse automorphism is $$F^{-1} = F^{m-1}$$ or $$\sqrt[p]{x}= x^{p^{m-1}}$$

The observation about normal bases of @Dilip Sarwate is excellent; also see http://en.wikipedia.org/wiki/Normal_basis