Finite Field Towers: Iterated Presentation and Complexity of Arithmetic,

Finite field towers GF(qP) are considered, where P=pn11Pn22••• pntt and all primes pi are distinct factors of (q – 1). Under this condition irreducible binomials of the form xP – c can be used for recursive extension of finite fields. We give description of an infinite sequence of irreducible binomials, new effective algorithms for fast multiplication and inversion in the tower, and finite and asymptotic estimates of arithmetic complexity. It is important that the achievable asymptotic estimate of the complexity has the form O(logQlogξlogQ), Q=qP, where log2γ≥ξ≥1 and γ is the minimal factor of q–1.