# NTRU Euclidean algorithm the inverse of f modulo p

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! • It is found by the Extended-GCD. If you write "find polynomial inverse modulo" these words into your search engine you will see. Almost all books mentions this, too. See from handbook applied cryptography page 82 Mar 4, 2021 at 7:46

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).

• Thank you, this is what I was hoping to see, I think I was using a invalid polynomial for my p(x). Thank you for your input! Mar 4, 2021 at 19:16
• Thanks, this has been useful for me too. I have a follow-up question: so the Euclidean algorithm usually only runs in Euclidean domains (ED) and when working mod 3 you're running it in $\mathbb{Z}_3[X]$ (right?) which I see is an ED because $\mathbb{Z}_3$ is a field. But if you're working mod 32, then could there be problems as $\mathbb{Z}_{32}[X]$ is no longer an ED?
– wdc
May 29, 2021 at 2:15