Hensel lift of a monic polynomial over $F_{2}$ in $Z_{8}$ Define the map - : $\mathbb{Z}_{p^{s}}\rightarrow \mathbb{F}_{p}$. Let g(x) be a monic polynomial over $\mathbb{F}_{p}$. A monic polynomial f(x) over $\mathbb{Z}_{p^{s}}[x]$ is called a Hensel lift of g(x) if $\overline{f}(x)=g(x)$ and there is a positive integer n not divisible by p such that $f(x)|(x^{n}-1)$ in $\mathbb{Z}_{p^{s}}[x]$. Otherwise, a monic polynomial g(x) over $\mathbb{F}_{p}$ has a Hensel lift f(x) over $\mathbb{Z}_{p^{s}}[x]$ if and only if g(x) has no multiple roots and $x\nmid g(x)$ in $\mathbb{F}_{p}[x]$.
Could you help me to find Hensel lift f(x) over $\mathbb{Z}_{8}$, if i have a monic polynomial g(x) has no multiple roots and $x\nmid g(x)$ in $\mathbb{F}_{2}[x]$?
For example, $g(x)=x^{3}+x+1\in\mathbb{F}_{2}[x]$.
 A: As $g(x)=x^3+x+1$ is a factor of $x^7-1$ in the ring $\mathbb{F}_2[x]$, and seven is the least exponent with this property, I am guessing that you are asking for a monic polynomial $f(x)\in\mathbb{Z}_8[x]$
such that $f(x)\equiv g(x)\pmod 8$, and $f(x)\mid x^7-1$ in the ring $\mathbb{Z}_8[x].$
The Hensel lifting will do exactly this for you, but
I will describe another algorithm for lifting a polynomial factor like this. It is, of course, equivalent to Hensel lifting, but it involves an IMHO neat trick I learned while playing with $\mathbb{Z}_4$-linear codes.
Let us first find a similar factorization modulo 4. We can view the polynomial $g(x)$ also as an element of the ring $\mathbb{Z}_4[x].$ Let us form the product
$$
(-1)^3g(x)g(-x)=(x^3+x+1)(x^3+x-1)=x^6+2x^4+x^2-1=g_2(x^2)
$$
in that ring. As the resulting polynomial is obviously even, we see that the
polynomial $g_2(x)=x^3+2x^2+x-1\in\mathbb{Z}_4[x]$ has the above property
$g_2(x^2)=-g(x)g(-x)$. Furthermore, because $g(-x)\equiv g(x)\pmod 2$, it follows
(by uniqueness of factorization in $\mathbb{F}_2[x]$ as well as the identity
$p(x^2)=p(x)^2$ that holds for all polynomials in $\mathbb{F}_2[x]$) that 
$$g_2(x)\equiv g(x)\pmod 2.$$
At  this point we record that $g_2(x)$ is the sought lifting in $\mathbb{Z}_4[x].$
Namely, you can easily verify that
$$
(x^3+2x^2+x-1)(x^4+2x^3-x^2+x+1)\equiv x^7-1 \pmod4.
$$
To get a lifting modulo 8 we repeat the dose. View $g_2(x)$ as a polynomial in
$\mathbb{Z}_8[x],$ and compute
$$
(-1)^3g_2(x)g_2(-x)=x^6-2x^4-3x-1=g_3(x^2),
$$
where $g_3(x)=x^3-2x^2-3x-1\in\mathbb{Z}_8[x].$ By a direct observation $g_3(x)\equiv g_2(x)\pmod 4$. The polynomial $g_3(x)$ is the answer. You can verify this by checking
that
$$
(x^3-2x^2-3x-1)(x^4+2x^3-x^2-3x+1)\equiv x^7-1 \pmod8.
$$

How can I justify this method? Let $\mathcal{O}$ be the ring of $2$-adic integers.
It follows from 2-adic theory that the quotient ring $\mathcal{O}[x]/\langle x^3+x+1\rangle$ is isomorphic to the ring of integers $R=\mathcal{O}[\zeta_7]$ of the unramified cubic extension of the field of 2-adic numbers. Here $\zeta_7$ is a
suitably chosen primitive seventh root of unity in $R$. This is because
the polynomial $g(x)=x^3+x+1$ splits into linear factors in $\mathbb{F}_8[x]$ and, by
Hensel lifting, also in $R[x]$. So we can write
$$
g(x)=x^3+x+1=(x-u_1)(x-u_2)(x-u_3)
$$
for some elements $u_1,u_2,u_3$ in $R$. Furthermore, reduction modulo two reveals
that (with an appropriate choice of indices) $u_1\equiv \zeta_7\pmod{2R}$,
$u_2\equiv \zeta_7^2\pmod{2R}$ and $u_3\equiv \zeta_7^4\pmod{2R}$.
By construction, the roots of $g_2(x)$ in $R$ are the squares of the roots of $g(x)$,
i.e. $u_i^2,i=1,2,3,$. But squaring the equations
$$
u_i=\zeta_7^{2^{i-1}}+2r_i,
$$
$r_i\in R, i=1,2,3,$ implies that
$$u_i^2=\zeta_7^{2^i}+4r_i\zeta_7^{2^{i-1}}+4r_i^2\equiv\zeta_7^{2^i}\pmod{4R}.$$
In other words, the zeros of $g_2(x)$ in $R/4R$ are primitive seventh roots of unity.
Repeating this calculation shows that the roots of $g_3(x)$ in $R/8R$ are
then also seventh roots of unity, which is basically what we wanted to achieve.
