Does a finite field ${\bf F}_q$, viewed as a vector space over another finite field, have a basis of squares? I am playing around with finite fields in Sage. I am viewing the finite field ${\bf F}_q$ as an vector space over a smaller field, ${\bf F}_{q'}$. If it helps, please feel free to assume that $q'$ is a prime (it is in the specific example I'm toying around with, but I hope that everything generalises to the case where the subfield is not necessarily a prime field).
Is it always possible to find a an ${\bf F}_{q'}$-basis of ${\bf F}_q$ consisting of squares? I guess we should set the characteristic $\ne 2$, or else of course the answer is yes. A nontrivial example I found is in the field ${\bf F}_{27} \cong {\bf F}_3[x]/(x^3+2x+1)$ has an ${\bf F}_3$-basis $\{1,\alpha^2+2\alpha+1, 2\alpha^2 + \alpha+1\}$, where we let $\alpha$ denote an element in the field with $\alpha^3 + 2\alpha + 1 = 0$. These are the squares of the elements $\{1, \alpha+1, \alpha^2+\alpha\}$.
It was pretty easy to come up with this by hand since the dimension is only $3$ and there aren't a whole lot of moving parts, but is there a way to find such a basis for general $q$ and $q'$? My suspicion is yes, since more than half of the elements of ${\bf F}_q$ are squares. And if the answer is indeed yes, is there an easy way to get Sage to compute it? (I am new to Sage, and so far have not even figured out how to tell Sage to consider ${\bf F}_{27}$ as a vector space over ${\bf F}_3$.)
 A: Yes, this is because the $\Bbb{F}_{q'}$ vector space generated by the elements of $\Bbb{F}_q^{\times 2}$ has at least $1+\frac{q-1}2$ elements.
And its cardinality is $(q')^m$ where $m$ is the $\Bbb{F}_{q'}$-dimension.
A: Yes.
Consider the homomorphism $\rho$ from $(\mathbb F_q^{\times}, \times)$ to itself defined by $\rho(x)=x^2$. Then $\ker \rho=\{\pm 1\}$.
If $p=2$, then $1=-1$, $\rho$ is injective and hence surjective. That is every element in $\mathbb F_q^\times$ is a square. Hence we may assume $p>2$ in the next.
Then we know that $\ker(\rho|_{\mathbb F_p})=\{\pm 1\}$, hence $\rho|_{\mathbb F_p}$ is not injective and further not surjective. Fix $x\in\mathbb F_p^\times\setminus \text{im}(\rho)$.
Note that $|\text{im}(\rho)| = |\mathbb F_q^{\times}|/2$ and $\mathbb F_q^{\times}/\rho({\mathbb F_q^{\times}})\cong\mathbb Z/2\mathbb Z$. Say we already have a basis $\{e_i\}$ of $\mathbb F_q$ over $\mathbb F_{q'}$. For each $e_i$, if $e_i$ is not a square, then we replace $e_i$ with $xe_i$ which is a square due to $x\rho(\mathbb F^{\times})=e_i\rho(\mathbb F^{\times})$ in $\mathbb F^{\times}/\rho(F^{\times})\cong\mathbb Z/2\mathbb Z$.
A: Even better: If $R$ is a commutative ring where $2$ is a unit, then every unital $R$-algebra is spanned (as an $R$-module) by squares. Namely, for every $\alpha$,
$$ \alpha = \tfrac12(\alpha+1)^2-\tfrac12\alpha^2-\tfrac12 1^2 $$
This holds in particular whenever $R$ is a field of characteristic $\ne 2$ and the algebra is a field extension.
This uses too many different squares to immediately give you a basis, but when you have a spanning set of a vector space, you can always select a subset that is a basis.
In particular, if you already know some basis $\{1,\alpha_2,\alpha_3,\ldots,\alpha_n\}$ for the extension field, then all you have to do is discard those elements of $\{1,\alpha_2^2,(\alpha_2+1)^2, \alpha_3^2, (\alpha_3+1)^2, \ldots, (\alpha_n+1)^2\}$ that are linear combinations of earlier elements in the list.

In characteristic 2, the argument in Just a user's answer takes care of the question when the fields are finite, but that's as far as we can go: If $K$ is any field of characteristic 2, then the field of fractions of $K[X]$ is an example of an extension that does not have a basis (over $K$) consisting of squares.
