If it weren't for the square-root in the last step of the Laguerre root-finding algorithm, the algorithm itself could operate over the p-adics (or just about anything that has a useful concept of derivative).
Is there an alternative operation that could be substituted for the square-root, even if that meant slower convergence?