Relaxed algorithms for \(p\)-adic numbers (Q449711)

The main theme of this paper is to replace the standard \textit{zealous} algorithms for \(p\)--adic numbers by new \textit{lazy} algorithms. The standard algorithms compute with truncated \(p\)--adic expansions at a precision specified by the user, combined with Newton-Hensel lifting techniques; they have an efficient asymptotic cost. The principle of lazy algorithms appeared for formal power series. It has advantages to solve implicit equations and does not need any choice from the user, but the first versions had a more expensive asymptotic cost than zealous algorithms. Here the Authors apply progress due to van der Hoeven to the case of \(p\)--adic numbers. They study in detail the elementary arithmetical operations and the computation of \(k\)--th roots. They have implemented their algorithms in the C++ library algebraix of Mathemagix.