How to use Frobenius for finding Square Roots in $GF(2^m)$ Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 &lt; n &lt; 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?
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$.