How to find the inverse of f(x) in NTRU key generation?

Question

I work on a project that depends on the NTRU cryptosystem, but I don't know how to find the inverse of $f(x)$.

Please see the picture:

Please help me to understand this problem.

Answer 1

$\newcommand{\Z}{\mathbb{Z}}$This somewhat oblique notation $F_q(x) = f(x)^{-1} \pmod q$ means that $F_q$ is the inverse of a unit element $f$ in the quotient $(\Z/q\Z)[x]/(P)$ of the polynomial ring $(\Z/q\Z)[x]$ by the ideal generated by some monic irreducible polynomial $P$ with integer coefficients. $P$ is a system parameter presumably defined in an earlier slide. Given $P$ and $f$, you can compute $F_q$ with the extended Euclidean algorithm.

The notation is presumably chosen because we variously map the same polynomial expressions with integer coefficients of $P$, $f$, and $g$ into three different polynomial rings, $\Z[x]$, $(\Z/q\Z)[x]$, and $(\Z/p\Z)[x]$ at different times. It wouldn't be quite right to say that $f$ is an element of $(\Z/q\Z)[x]/(P)$, because in the next sentence $f$ will be an element of $(\Z/p\Z)[x]/(P)$ instead. Saying $a(x) = b(x) \pmod q$ means we are taking the base ring of the polynomials $a$ and $b$ to be $\Z/q\Z$ for that equation.