# NTRU Encryption

It's using Euclidian inverse. Can you show it step by step?

$$N=7, q=11, a = 3+2X^2 -3X^4 +X^6$$

the inverse of $a \pmod {11}$ is

$$A=-2+4X+2X^2 +4X^3 -4X^4 +2X^5 -2X^6$$

How do we compute $A$?

-
Actually, it is duplicated: crypto.stackexchange.com/questions/6654/… – cygnusv Mar 26 at 8:48

At least it checks out:

$$(3 + 2X^2 - 3X^4 + X^6)(-2 + 4X + 2X^2 + 4X^3 - 4X^4 + 2X^5 - 2X^6) = -6 + X + 6X^2 + X^3 - X^4 + 6X^5 - 6X^6 - 4X^2 + 8X^3 + 4X^4 + 8X^5 - 8X^6 + 4 - 4X + 6X^4 - X^5 - 6X^6 - 1 + X - 6X^2 + 6X^3 - 2X^6 + 4 + 2X + 4X^2 - 4X^3 + 2X^4 - 2X^5 = 1$$ multiplying out all the terms, using $X^7 = 1, X^8 = X, X^9 = X^2$ etc. and the fact that all coefficients are taken mod 11.

In this answer by some NTRU person you will find the algorithm to find it. Try and follow that.

-