Hensel lifting is a beautiful technique used to solve

polynomial congruences of the form f(x) ≡ 0 (mod p

^{i}), where p is

prime. Beauty aside, Hensel lifting is also a very

*useful* technique. In fact, I believe that Hensel does most of his heavy lifting in the field of

cryptography.

The idea is simple. Suppose we have a root a of f(x) modulo p^{i}. We hope to find a solution to f(x) modulo p^{i+1} building off of our root a in the sense that the root mod p^{i+1} is congruent to a mod p^{i}. Such a root would have to have the form a + np^{i} for some integer n. So we want to try and find an n such that f(a + np^{i}) ≡ 0 (mod p^{i+1}).

In order to find such a number n, we use the Taylor series expansion for f(x) about our original solution a. Note that there is no notion of continuity in this context. The Taylor series expansion does, however, work as a polynomial identity, where we take the required derivatives formally as most of us have been trained to do anyway. The expansion that we are interested in is

f(a + np^{i+1}) = f(a) + np^{i}f'(a) + (np^{i})^{2}f''(a)/2! + ... + (np^{i})^{r}f^{(r)}(a)/r!, where r is the degree of f(x).

Note that in the derivative f^{(k)}(x), each coefficient is a multiple of some product of k consecutive integers. As a result, each of the coefficients in f^{(k)}(x) is divisible by k!. But that implies that the expression f^{(k)}(a) is a multiple of k!. Thus f^{(k)}(a)/k! is an integer for each k.

By our observation above, and since p^{ki} > p^{i+1} for k ≥ 2, we have that f(a + np^{i}) ≡ f(a) + np^{i}f'(a) (mod p^{i+1}).

In order for a + np^{i} to be a root of f(x) modulo p^{i+1}, then, we need to have that np^{i}f'(a) ≡ f(a) (mod p^{i+1}). If we rewrite this as np^{i}f'(a) = -f(a) + tp^{i+1}, since f(a) is divisible by p^{i} by assumption, we can reduce our problem to finding an n that satisfies nf'(a) ≡ -f(a)/p^{i} (mod p). This is a linear congruence in n. A linear congruence modulo a prime! Piece of cake.

In fact, if f'(a) is nonzero mod p, there is a unique solution n, which gives us the lift a - f(a)/f'(a) of a, where 1/f'(a) is the inverse of f'(a) in Z_{p}. So basically, Hensel lifting is like performing Newton's method in the case that f'(a) stays nonzero modulo p.

This is just a brief overview of the technique. More observations can be made, of course, but I shall leave them to the investigations of the reader.