HenselLift

The -adic root of a polynomial that reduces to `seed` mod , by Newton's iteration — Hensel's lemma made to run. `AdicSqrt` is the special case .

HenselLift(f, seed, b, prec?)needs and a unit mod ; in one free variable

AdicSqrt(x, prec?)a square root in , prime ; declines when there is none

Domain: Numeral systems

Details

Each Newton step doubles the number of correct digits, so 20 digits take five steps
The result is capped at `prec` (default 20): a root found this way is known modulo and nothing more, which is where capped values come from
A root with is not simple and does not lift this way — from 1 in declines
Composite works when is coprime to , and that is how the non-rational elements of appear: from 5 lifts to the idempotent
Square roots: an odd prime needs to be a quadratic residue mod ; needs and starts the iteration one level up, since is not a unit

Examples