In NTRU, we know that $f$ is a ternary polynomial in the ring $$R=\frac{\mathbb{Z}_q[x]}{x^n-1}.$$ Here $f$ has $d+1$ coefficients 1 and $d$ coefficients $-1$ and rest are zero. For computing the public key, it is known that $$h=f^{-1}g$$ where $g$ is also a ternary polynomial with $d$ coefficients 1 and $d$ coefficients $-1$ and rest are zero.

Is there any result that informs about the possible degrees of $f^{-1}$? My main doubt is what if it is small enough?


1 Answer 1


We would typically calculate $f^{-1}$ using the extended Euclidean algorithm, so that it has degree at most $n-1$ and typically has degree exactly $n-1$.

  • $\begingroup$ How it would typically be $n-1$? $\endgroup$
    – PAMG
    Apr 2 at 6:56
  • $\begingroup$ @PAMG Because more than a proportion $(q-1)/q$ of elements of $R^*$ have degree $n-1$. $\endgroup$
    – Daniel S
    Apr 2 at 8:49
  • $\begingroup$ Can you please explain it how? $\endgroup$
    – PAMG
    Apr 2 at 8:54
  • 1
    $\begingroup$ @PAMG balls and bins probability! There are possible $q$ balls one can put into the bin ( the $n-1$ degree monomial) of which one is zero. Zero makes, a degree not equal to $n-1$. Now clear? $\endgroup$
    – kelalaka
    Apr 2 at 10:33
  • $\begingroup$ Yes. Thank you. $\endgroup$
    – PAMG
    Apr 2 at 11:12

Your Answer

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

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