# 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 – kelalaka Mar 4 at 7:46

## 1 Answer

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! – Daftyler Mar 4 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? – dcw May 29 at 2:15