Fast arithmetic in unramified \(p\)-adic fields (Q973961)

For a prime \(p\) let \(\mathbb Z_p\) be the ring of \(p\)-adic integers, \(\mathbb Z_{p^n}\) a degree \(n\) unramified extension of \(\mathbb Z_p\), represented as \(\mathbb Z_p[x]/\varphi(x)\) for some inert polynomial \(\varphi(x)\in\mathbb Z_p[x]\) of degree \(n\) and precision \(p^N\) for an integer \(N \geq 1\) -- in notation \(\mathbb Z_{p^n} \bmod {p^N}\). The author adapts a result of \textit{K. Kedlaya} and \textit{C. Umans} [Fast modular composition in any characteristic. In: Proc. 49th IEEE FOCS, 146--155 (2008)] on modular composition of polynomials to polynomials in \(\mathbb Z_p[x]\bmod {p^N}\). Applying this result fast, deterministic algorithms for common operations in \(\mathbb Z_{p^n} \bmod p^N\) are obtained, like Newton iteration, Galois conjugation, computing minimal polynomials, traces, norms.