# Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

I have the polynomial ring $$R = \mathbb{Z}[X]/(X^N - 1)$$ with $$N = 11$$ and $$h \in R$$ with $$\begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{equation*}$$ Now I want to find the polynomial $$u$$ such that $$\begin{equation*} u\cdot h + v\cdot (X^N - 1) \equiv X - 1 \ (\textrm{mod} \ 32) \end{equation*}$$ where we assume $$\gcd(h, X^N - 1) = X - 1$$ reducing coefficients $$\textrm{mod} \ 32$$. If we also let $$*$$ denote the multiplication in $$R$$, I can easily find $$u$$ such that $$u*h \equiv X - 1 \ (\textrm{mod} \ 2)$$ using the extended Euclidean algorithm, and it's $$u = 1+X+X^{4}+X^{5}+X^{9}$$, but I'm having issues using this to construct the solution such that $$u' * h \equiv X - 1 \ (\textrm{mod} \ 32)$$. Can someone outline an algorithm or link me some reading material on how to do this?

• Maybe this question should be moved to math SE, there is no crypto related question in here
– tylo
Nov 22, 2020 at 16:58
• Thank you. The reason I asked in crypto SE is because this is a part of an attack on the NTRU cryptosystem where an unpadded message block $m$ has been encrypted with different randomly generated $\phi_i \in L(3, 3)$, that is $\phi_i \in R$ where three of its coefficients are 1, and three of its coefficients are -1 with the rest being 0. The first step in this attack is to find the $u$ in my original question. Nov 23, 2020 at 1:11

• First, you need to express your element as a root of a function: $$g(u)= hu - (X-1)$$