Computing in degree $$2^k$$ -extensions of finite fields of odd characteristic.

We show how to perform basic operations (arithmetic, square roots, computing isomorphisms) over finite fields of the form $$\mathbb F _{q^{2^k}}$$ in essentially linear time. [ABSTRACT FROM AUTHOR]