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

Question

Can we define a function similar to square root for $G = GF(2^m)$ (Galois field with $2^m$ elements) as $\sqrt{x} = y$ if $y^2 = y \cdot y = x$ ? For which elements $x \in G : \exists y \in G : y^2 = x$ this function would be defined?

Can I approach this question like this:

If we can generate all elements of $G$ except $0$ from another element $a$ as $a^k : k = 1 \ldots (2^m-1)$, then any $x \neq 0$ can be expressed as $x=a^r$ for some $r$ and $y$ would be also $y = a^s$ for some $s$. $y^2 = x$ means that $$r = 2s \mod 2^m-1$$ $$r,s \in 0 \ldots 2^m-2$$

It looks like I can find $s$ for any $r$ to satisfy equation. That would mean that there is a "square root" for any element in $G$, right?

PS: I'm looking into options to analyze streams of data (bytes, 16 bit or 32 bit integers) as part of another computational task, therefore only specific Galois fields are interesting for me: $GF(2^m)$. Be prepared that I can be way off in the field theory, that was very long time since I touched it - but any comments are welcome!

Answer 1

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.

Answer 2

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.

Answer 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

Answer 4

Another way to look at it:

If we are working in a field of characteristic $2$, the derivative of $X^2-a$ is $0$. This implies that the two roots of $X^2-a$ coincide, so square roots, when they exist, are unique.

In other words, the map $b\mapsto b^2$ is injective. If our field is finite, this map must be surjective as well.

Answer 5

If GF(2^m) is small enough to use log and exponentiate tables, then square root of x can be implemented using tables, log[] and exp[]

L = log(x)
if (L is odd) L = L + 2^m - 1
E = L / 2
square root = exp(E)

If GF(2^m) is too large to use log and exponentiation tables, there is an alternative method. GF(2^m) is isomorphic to its field of square roots, since if a + b = c and a • b = d, then (a + b)^2 = a^2 + b^2 = c^2, and (a • b)^2 = a^2 • b^2 = d^2. The elements of GF(2^m) can be mapped to their square roots using an m by m matrix with 1 bit elements, where the values in the columns represent powers of the square root of 2 which is 2^((2^m)/2), which can be quickly calculated using exponentiation by squaring:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Let σ = sqrt(2), then the square roots of 0 and powers of 2 are:

S[0] = 0
S[1] = 1
S[2] = σ
S[4] = S[2] • σ
S[8] = S[4] • σ
...

For the mapping matrix, the columns are indexed by powers of 2, and the values in the columns are the square roots of those powers of 2. For example, GF(2^8) with reducing polynomial x^8 + x^4 + x^3 + x^2 + 1 (hex 11D), treat an element of GF(2^8) as a matrix E[8][1], and the mapping matrix below as M[8][8], then the square root S[8][1] = M[8][8] • E[8][1] (carryless multiply since these are 1 bit elements of GF(2)).

80 40 20 10 08 04 02 01    value of E

 0  0  0  0  0  0  1  0
 1  0  0  0  0  0  0  0
 0  0  1  0  0  0  0  0
 1  0  0  0  1  0  0  0    mapping
 1  1  1  0  0  0  0  0    matrix
 1  0  1  1  1  0  1  0
 0  0  1  0  1  1  0  0
 0  0  0  0  1  0  1  1

5c 08 2e 04 17 02 85 01    value of S