How to find the inverse of a polynomial in NTRU-PKCS
Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits.

The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i&lt;n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i&lt;n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial multiplication performed modulo $x^n-1$, $F\cdot F_q\equiv1\pmod q$ and $F\cdot F_p\equiv1\pmod p$, or determine that's impossible.

We can treat the problem for $F_q$. The same method will apply for $F_p$. Alternatively, since $q$ and $p$ are coprime, we can find $H$ with $F\cdot H\equiv1\pmod{(p\,q)}$ and if it exists reduce its coefficient modulo $q$ and $p$ to find the $q_i$ and $p_i$ (but if there's no $H$, we could only conclude that at least one of $F_q$ or $F_p$ does not exist).



One conceptually simple method is to see the problem as a system of $n$ linear equations in $\Bbb Z_q$, with $n$ unknowns $q_i$, obtained by using the question's definition for the equivalent equation $F_q\cdot F\equiv1\pmod q$:
$$\forall k\in[0,n-1),\quad \sum_{0\le i&lt;n}q_i\,f_{(k-i\bmod n)}\equiv\begin{cases}1&amp;\text{if }k=0\\0&amp;\text{otherwise}\end{cases}\pmod q$$
and use Gaussian elimination.
If we use the question's $F=1+x^3-x^4-x^5$ for $n=7$, that linear system goes$$
q_0-q_2-q_3+q_4\equiv1\pmod q\\
q_1-q_3-q_4+q_5\equiv0\pmod q\\
q_2-q_4-q_5+q_6\equiv0\pmod q\\
q_3-q_5-q_6+q_0\equiv0\pmod q\\
q_4-q_6-q_0+q_1\equiv0\pmod q\\
q_5-q_0-q_1+q_2\equiv0\pmod q\\
q_6-q_1-q_2+q_3\equiv0\pmod q$$
that is, by realigning$$\begin{matrix}
+q_0&amp;    &amp;-q_2&amp;-q_3&amp;+q_4&amp;    &amp;    &amp;\equiv1\pmod q\\
    &amp;+q_1&amp;    &amp;-q_3&amp;-q_4&amp;+q_5&amp;    &amp;\equiv0\pmod q\\
    &amp;    &amp;+q_2&amp;    &amp;-q_4&amp;-q_5&amp;+q_6&amp;\equiv0\pmod q\\
+q_0&amp;    &amp;    &amp;+q_3&amp;    &amp;-q_5&amp;-q_6&amp;\equiv0\pmod q\\
-q_0&amp;+q_1&amp;    &amp;    &amp;+q_4&amp;    &amp;-q_6&amp;\equiv0\pmod q\\
-q_0&amp;-q_1&amp;+q_2&amp;    &amp;    &amp;+q_5&amp;    &amp;\equiv0\pmod q\\
    &amp;-q_1&amp;-q_2&amp;+q_3&amp;    &amp;    &amp;+q_6&amp;\equiv0\pmod q\end{matrix}$$
The matrix of coefficients is circulant, and its last line has the coefficients of $F$ in reverse order.

This one happens to have no solution except for $q=1$: if we sum all the lines we get $0\equiv1\pmod q$. Mere generally, except for $q=1$, there can't be a solution when $0=\sum f_i$ as in the example.

While we could in general solve the system (or find that it has no solution) by Gaussian elimination and careful application of arithmmetic in $\Bbb Z_q$, that has cost $\mathcal O(n^3\,\log q\,\log\log q)$ and uses $\mathcal O(n^2\,\log q)$ memory. And while there are better methods for a circulant matrix, I won't go further into that. 



Better methods to solve this problem are derived from the Extended Euclidean Algorithm, which given $A$ and $B$ in a principal ring, finds $U$ and $V$ in that ring with $A\cdot U+B\cdot V=G$, where $G$ is the Greatest Common Divisor of $A$ and $B$. As a byproduct that gives the modular inverse $U$ of $A$ modulo $B\ne0$, or tells that it does not exist when $G\ne1$.

That algorithm finds the inverse in particular in these rings:


The ring $\Bbb Z_q$ (the integers), where for non-negative $a$ and $b$ it can go:


If $b=0$, output "$a$ has no inverse modulo $b$" and stop.
$c\gets a$, $d\gets b$, $u\gets0$ and $v\gets1$.
Repeat


If $c=0$, output "$a$ has no inverse modulo $b$" and stop.
If $c=1$, output "the inverse of $a$ modulo $b$ is $v$" and stop.
Perform Euclidean division of $d$ by $c$ yielding quotient $z$ and remainder $r$ with $0\le r&lt;c$.
$d\gets r$ and $u\gets u+z\cdot v$.
If $d=0$, output "$a$ has no inverse modulo $b$" and stop.
If $d=1$, output "the inverse of $a$ modulo $b$ is $b-v$" and stop.
Perform Euclidean division of $c$ by $d$ yielding quotient $z$ and remainder $r$ with $0\le r&lt;d$.
$c\gets r$ and $v\gets v+z\cdot u$


The ring of polynomials with coefficients in the field $\Bbb Q$ (the rationals), where it can go:


If $B=0$, output "$A$ has no inverse modulo $B$" and stop.
$C\gets A$, $D\gets B$, $U\gets0$ and $V\gets1$.
Repeat


If $C=0$, output "$A$ has no inverse modulo $B$" and stop.
If $C$ has degree $0$ (that is, has only term $c_0$), output "the inverse of $A$ modulo $B$ is $(1/c_0)\,V$" and stop.
Perform polynomial division of $D$ by $C$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $C$.
$D\gets R$ and $U\gets U+Z\cdot V$.
If $D=0$, output "$A$ has no inverse modulo $B$" and stop.
If $D$ has degree $0$ (that is, has only term $d_0$), output "the inverse of $A$ modulo $B$ is $(-1/d_0)\,V$" and stop.
Perform polynomial division of $C$ by $D$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $D$.
$C\gets R$ and $V\gets V+Z\cdot U$.


The ring of polynomials with coefficients in a finite field $\Bbb Z_p$ for prime $p$: same as above, except that when a coefficient $\displaystyle\frac st$ is obtained, we replace it with the integer $0$ when $s=0$, or otherwise with the integer $(t/\gcd(s,t))^{-1}\,(s/\gcd(s,t))\bmod q$.


The later is exactly what we need for $F_p$: we feed $A=F$ and $B=x^n-1$ to the algorithm, and it computes $F_p=A^{-1}\bmod B$ (or tells that is does not exists).

However, for a composite $q$, it can appear $\displaystyle\frac st$ that can no be brought back in $\Bbb Z_q$ because $\gcd(t,q)\ne1$.

I'm not sure about:


If we can conclude that when we hit the problem, we can stop and conclude that $F$ is not invertible.
If we can compute the inverse in the ring of polynomials with coefficients in the field $\Bbb Q$, and reduce in the end. I think we could find that $F$ is not invertible, but it really is invertible modulo $q$.


When $q$ is the product of distinct primes, we can get around that by finding the inverse modulus each prime dividing $q$, and using the Chinese Remainder Theorem to work back the coefficients of the inverse modulo $q$. We do not need to know the factorization of $q$ in advance: when we hit the problem, the GCD gives us a (perhaps partial) factorization of $q$. However I'm not sure of what to do when $q$ is divisible by a square of a prime.

Under work: further straighten that, example.



For a full-blown, faster method, see Joseph H. Silverman, Almost Inverses and Fast NTRU Key Creation, NTRU Technical Report #014, 1999.