Arithmetic of finite fields (Q1167763)

Let \(p\) be a fixed prime and \(n=m_1m_2\cdots m_l\) be a factorization of a positive integer \(n\) such that \(m_1\ge m_2\ge \ldots\ge m_l\ge 1\). The author proposes an algorithm for realizing the finite field \(\mathrm{GF}(p^n)\) with \(p^n\) elements, by the chain of field extensions \[ \mathrm{GF}(p)\subseteq \mathrm{GF}(p^{m_1})\subseteq \mathrm{GF}(p^{m_1m_2}) \subseteq \ldots\subseteq \mathrm{GF}(p^{m_1m_2\cdots m_l}) = \mathrm{GF}(p^n). \] The algorithm requires for each \(i\), \(1\le i\le l\), to find an irreducible polynomial of degree \(m_i\) in \(\mathrm{GF}(p^{m_1m_2\cdots m_{l-1}})[x] \) \((m_1m_2\cdots m_{l-1} = 1\) if \(i = 1)\). The author claims that his method, on appealing in each step of extensions to the best algorithm known so far finding irreducible polynomials over finite fields, can improve the run-time of constructing \(\mathrm{GF}(p^n)\) with usual procedure, by an \(n^{1/2}\) factor for most (non-prime) integers \(n\).