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?

  • $\begingroup$ Maybe this question should be moved to math SE, there is no crypto related question in here $\endgroup$
    – tylo
    Nov 22, 2020 at 16:58
  • $\begingroup$ 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. $\endgroup$ Nov 23, 2020 at 1:11

1 Answer 1


One way to raise solutions to higher powers of the modulus is Hensel's Lemma.

  • First, you need to express your element as a root of a function: $g(u)= hu - (X-1)$
  • Find the solution modulo 2, which you already did.
  • Use the Lemma to raise this solution to higher powers of 2. Maybe it is useful to do this in several steps. Find the solutions mod 4,8,16 and then 32.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.