Hensel lifting (idea)

Hensel lifting is a beautiful technique used to solve polynomial congruences of the form f(x) ≡ 0 (mod pⁱ), 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ⁱ. We hope to find a solution to f(x) modulo pⁱ⁺¹ building off of our root a in the sense that the root mod pⁱ⁺¹ is congruent to a mod pⁱ. Such a root would have to have the form a + npⁱ for some integer n. So we want to try and find an n such that f(a + npⁱ) ≡ 0 (mod pⁱ⁺¹).

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ⁱ⁺¹) = f(a) + npⁱf'(a) + (npⁱ)²f''(a)/2! + ... + (npⁱ)^rf^(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ⁱ⁺¹ for k ≥ 2, we have that f(a + npⁱ) ≡ f(a) + npⁱf'(a) (mod pⁱ⁺¹).

In order for a + npⁱ to be a root of f(x) modulo pⁱ⁺¹, then, we need to have that npⁱf'(a) ≡ f(a) (mod pⁱ⁺¹). If we rewrite this as npⁱf'(a) = -f(a) + tpⁱ⁺¹, since f(a) is divisible by pⁱ by assumption, we can reduce our problem to finding an n that satisfies nf'(a) ≡ -f(a)/pⁱ (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.