NTRU Euclidean algorithm the inverse of f modulo p

Question

I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling to understand how to practically do the inverse of f. I know that this is solved using the Euclidean algorithm, but I am unable to figure out what the steps would be. I was hoping someone would be able to show the steps to solve the example shown on the NTRUEncrypt wiki page shown below (fp or fq), or a smaller polynomial that gets the point across. I am more interested in the practical steps then the theory behind it, as I have found many resources for that.

Thank you!

Answer 1

I'll try to follow a similar notation to the example on wikipedia

Our initial inputs are $p(x) = x^{11}-1$ which defines the ring and $a(x)=-x^{10}+x^9+x^6-x^4+x^2-1$ and working mod 3 rather than the mod 2 example on wikipedia.

For step 1 we have quotient $q_1(x)=2x+2$ and remainder $r_1(x)=x^9+x^7+x^6+2x^5+2x^4+x^3+2x^2+1$ so that $t_1=x+1$.

For step 2 we have quotient $q_2=2x+1$ and remainder $r_2=x^8+2x^6+x^4+x^3+2x^2+2x+1$ and $t_2=x^2$.

For step 3 we have quotient $q_3=x$ and remainder $r_3=2x^7+x^6+x^7+x^4+2x^3+2x+1$ and $t_2=x^3+x+1$.

For step 4 we have quotient $q_4=2x+2$ and remainder $r_4=x^6+2x^5+x^4+x^2+2x+2$ and $t_4=2x^4+2x^3+2x^2+2x+1$.

For step 5 we have quotient $q_5=2x$ and remainder $r_5=2x^5+x^4+2x^2+x+1$ and $t_5=2x^5+2x^4+x^3+2x^2+2x+1$.

For step 6 we have quotient $q_6=2x$ and remainder $r_6=x^4+2x^3+2x^2+2$ and $t_6=x2x^6+2x^5+x^3+x^2+1$.

For step 7 we have quotient $q_7=2x$ and remainder $r_7=2x^3+2x^2+1$ and $t_7=x2x^7+2x^6+2x^5+2x^3+2x^2+1$.

For step 8 we have quotient $q_8=2x+2$ and remainder $r_8=x^2+x$ and $t_9=2x^9+x^8+2*x^7+x^5+2x^4+2x^3+2x+1$.

For step 9 we have quotient $q_9=2x$ and remainder $r_9=1$ and $t_9=2x^9+x^8+2x^7+x^5+2x^4+2x^3+x+2$, which is the required inverse.

I'll leave the mod 32 example as an exercise (sagemath is your friend).