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:

Example of NTRU key generation

Please help me to understand this problem.


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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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