# Degree of inverse of f in NTRU?

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?

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$$.

• How it would typically be $n-1$?
– PAMG
Commented Apr 2 at 6:56
• @PAMG Because more than a proportion $(q-1)/q$ of elements of $R^*$ have degree $n-1$. Commented Apr 2 at 8:49
• Can you please explain it how?
– PAMG
Commented Apr 2 at 8:54
• @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? Commented Apr 2 at 10:33
• Yes. Thank you.
– PAMG
Commented Apr 2 at 11:12