I am coding a java based implementation of the nTRU public key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled **The Problem**.


The key $F$ is a polynomial chosen from a set of polynomials of degree $x^n-1$, that is to say, $F$ is always of the form: 

$$a_0 x^0 + a_1 x^1 + \cdots + a_{n-1} x^{n-1} \text{ where } a_i \in \{0, 1,-1\}.$$

An example of $F$ (where $n=7$) is:

 $$1x^0 + 0x^1 + 0x^2 + 1x^3 + -1x^4 + -1x^5 + 0x^6$$

or more plainly:

$$1 + x^3 - x^4 -x^5$$

  

$F$  functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$

$F_q$ and $F_p$ are of the same form as $f$ (polynomials of degree $x^{n-1}$) except their integer coefficients are $a$ : 

$$0 \leq  a < p \text{ or } q$$ where $p$ and $q$ are predefined integers ($p$ is prime, $q$ is coprime with $p$)


$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot  F_q = 1 \pmod{q}$$


$$\big( F \cdot  F_q = [ 1x^0 + 0x^1 + 0x^2 + 0x^3 + 0x^4 + 0x^5 + 0x^6 ] \pmod{q} \big)$$

and same for $F \cdot F_p = 1 \pmod p$
 

Adding and subtracting these polynomials functions normally however multiplying these polynomials works different, given two polynomial $a$ and $b$ of degree $x^{n-1}$:

$$a \cdot b = c_0\cdot x^0 + c_1\cdot x^1 + \cdots + c_{n-1}\cdot x^{n-1} = c$$

where each coefficient $c_k$ is calculated by: $$c_k=\sum_{0\le i<n-1}a_i\,b_{(k-i\bmod n)}$$

multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial doesn't exceed degree $x^{n-1}$ 

with all that being said...


**The Problem**

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F,F_p$, and $F_q$ for $$F\cdot F_q = 1 \pmod{q}$$ and for $p$ etc.


Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $f$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.