Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as described in the answer to this related question? And why? (anecdote or rigid proof are both welcome).

For example, given $f(x) = x^2 + 1$

By trial and error, $x^{2^{n-1}}$ with generators $x^{257} + x^{12} + 1$ and $x^3 + x + 1$, both yield $x + 1$.

Of course, for an efficient algorithm, the smaller the degree, the faster the $x^{2^{n-1}}$ computation. But computing a generator for every degree that might be needed (or as needed) would be daunting. Instead, and assuming one can rely upon the general case, i.e., "any primitive generator having degree greater than that of $x$ will do", one can use a table from a source like this (A Table of Primitive Binary Polynomials - M. Zivkovic et al).

I am very new to finite fields and haven't got all the terminology much less the understanding correct, so I hope the example clarifies my question.

EDIT: Background

Consider the Galios relationship: $S_j = S_0 x^j mod P$, where S, x, and P are all polynomials with coefficients in GF(2). $P$ is not irreducible in this case. So, to determine the period of $P$, it must be factored, and by finding the derivative of $P$ to be 0, we know a square exists. The referenced answer says that by the Frobenius automorphism, the square root of a polynomial is $x^{2^{n-1}}$. But in this case, $n$ and an $r(t)$ are not given. Can they be chosen specially for the case of $P$? For instance, can $n$ be set to $degree(P) + 1$ and can $r(t)$ be chosen with $degree(n)$ from a table of known irreducibles?

  • Yes, modulus $r(t)$ is not given (which is part of the reason for question). And yes, the example has a trivial result, but is informative when derived by use of the larger generator. I will update my question further with more background. – Les Jul 31 at 12:24
  • Are you aware that factoring polynomials is easy? – fkraiem Jul 31 at 13:05
  • Basically it seems that you just want to factor a polynomial with coefficients in $\mathbf F_2$ into a product of irreducible factors. This is completely unrelated to the comptation of square roots in extension fields. – fkraiem Jul 31 at 13:18
  • In the linked blog posts I talk about the algorithms for polynomial factoring, but you don't need to study them if you just want to factor polynomials; plenty of people have implemented those algorithms so you don't have to. – fkraiem Jul 31 at 15:17
up vote 2 down vote accepted

No, the relation you have noticed does not work in general, and it is easy to find counterexamples. For example using the two following representations of $\mathbf F_8$.

In $\mathbf F_2[X]/(X^3+X^2+1)$, the square root of (the coset of) $X$ is $X^2+X+1$, whereas in $\mathbf F_2[X]/(X^3+X+1)$ it is $X^2+X$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.