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$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ stackoverflow.com/questions/2421409/… $\endgroup$ – cygnusv Mar 26 '15 at 8:25
-
1$\begingroup$ Actually, it is duplicated: crypto.stackexchange.com/questions/6654/… $\endgroup$ – cygnusv Mar 26 '15 at 8:48
Add a comment
|
$\begingroup$
$\endgroup$
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.
