Monthly Archives: May 2016

Hensel’s lifting

0
Posted on by

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

We start with the trivial

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.