# Hensel’s lifting

0

Number theory is full of gems that turn into effective algorithms demanded in cryptography. Consider the congruence

$x N \equiv 1 \mod R$

where N is odd, and R > N is a power of 2.

Probably the most effective algorithm to solve it is based on the Hensel’s lemma; the corollary that applies for our congruence is: suppose we know the solution $x_{k-1}$ for $R=2^{k-1}$ :

$x_{k-1}N \equiv 1 \mod 2^{k-1}$

then the solution $x_k$ for

$x_k N \equiv 1 \mod 2^k$

is either $x_{k-1}$ or $x_{k-1} + 2^{k-1}$

Example: solve

$x \cdot 21 \equiv 1 \mod 32$

$x_1 \cdot 21 \equiv 1 \mod 2$

which can be nothing else but $x_1 = 1$; next,

$x_2 \cdot 21 \equiv 1 \mod 4$

which can be either $x_2 = 1$ or $x_2 = 1 + 2 = 3$; checking the first alternative gives $1\cdot 21\ and\ 3 = 1$, so $x_2=1$; next,

$x_3 \cdot 21 \equiv 1 \mod 8$; checking $x_3 = x_2 = 1$ gives $1\cdot 21\ and\ 7 = 5$, so $x_3=x_2+4=5$; next,

$x_4 \cdot 21 \equiv 1 \mod 16$; checking $x_4 = x_3 = 5$ gives $5\cdot 21\ and\ 15 = 9$, so $x_4=x_3+8=13$; finally,

$x_5 \cdot 21 \equiv 1 \mod 32$; checking $x_5 = x_4 = 13$ gives $13\cdot 21\ and\ 31 = 17$, so $x_5=x_4+16=29$.

The solution of the congruence is $x = 29$.