Finite field towers: Iterated presentation and complexity of arithmetic. (Q1609402)

Let \(p_k\), \(k = 1, \ldots, t\), be prime divisors of \(q-1\) and \(q \equiv 1\bmod 4\) if \(2 \in \{p_1,\ldots, p_t\}\). Suppose that \(P = p_1^{n_1}p_2^{n_2}\cdots p_t^{n_t}\). It is shown that then the field \(\mathbb F_{q^P}\) can be represented as a tower of extensions of \(\mathbb F_q\) generated by irreducible binomials. Based on this fact a fast multiplication and a fast inversion algorithm in the field \(\mathbb F_{q^P}\) is established and the complexity of these algorithms is analyzed.