Hensel lifting is a beautiful technique used to solve polynomial congruences of the form f(x) ≡ 0 (mod pi), 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 pi. We hope to find a solution to f(x) modulo pi+1 building off of our root a in the sense that the root mod pi+1 is congruent to a mod pi. Such a root would have to have the form a + npi for some integer n. So we want to try and find an n such that f(a + npi) ≡ 0 (mod pi+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 + npi+1) = f(a) + npif'(a) + (npi)2f''(a)/2! + ... + (npi)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 pki > pi+1 for k ≥ 2, we have that f(a + npi) ≡ f(a) + npif'(a) (mod pi+1).

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

Log in or registerto write something here or to contact authors.