Polynomial ring over finite field - inverting a polynomial non-prime

Question

I'm trying to recreate the wiki's example procedure, available here:

https://en.wikipedia.org/wiki/NTRUEncrypt

I've run into an issue while attempting to invert the polynomials.

The SAGE code below seems to be working fine for the given p=3, which is a prime number.

However, the representation of the polynomial in the field generated by q=32 ends up wrong, because it behaves as if the modulus was 2.

Here's the code in play:

F = PolynomialRing(GF(32),'a')
a = F.gen()
Ring = F.quotient(a^11 - 1, 'x')
x = Ring.gen()
pollist = [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]

fq = Ring(pollist)
print(fq)
print(fq^(-1))

The Ring is described as follows:

Univariate Quotient Polynomial Ring in x over Finite Field in z5 of size 2^5 with modulus a^11 + 1

And the result:

x^10 + x^9 + x^6 + x^4 + x^2 + x + 1
x^5 + x + 1

I've tried to replace the Finite Field with IntegerModRing(32), but the inversion ends up demanding a field, as implied by the message:

NotImplementedError: The base ring (=Ring of integers modulo 32) is not a field

The desired result:

$fq(x) = 5+9X+6X^2+16X^3+4X^4+15X^5+16X^6+22X^7+20X^8+18X^9+30X^{10} (mod32)$

Any suggestions as to how I could obtain the correct inverse of f (mod q) would be greatly appreciated.

Answer 1

NTRU definitely does its arithmetic inside a ring like $\Bbb{Z}_q[X]/(X^N-1)$, so using the field $\Bbb{F}_q$ in place of $\Bbb{Z}_q$ is not right.

I am willing to take the error message at face value. The people behind Sage simply haven't implemented the calculation of inverses in rings like $R_m:=\Bbb{Z}_{2^m}[X]/(X^N-1)$ (IIRC in NTRU $q$ is always a power of two).

Here's how I would do it. First a general explanation, then your example:

Begin by calculating the inverse of $f$ in $R_1$, i.e. the inverse modulo $2$ and $X^N-1$. We need to view the coefficients of that inverse as integers rather than as elements of $\Bbb{Z}_2$. I don't know how to do that in Sage, but looks like the tricks you did with pollist is all you need to go back and forth.

At this point we have a polynomial $g_1(x)\in\Bbb{Z}[x]$ such that $$f(x)g_1(x)=1+2r_1(X)+(X^N-1)h_1(X)$$ for some polynomials $r_1(X),h_1(X)\in\Bbb{Z}[x]$. For what follows it is cleaner to write this as $$f(x)g_1(x)=1+2r_1(x)\in \Bbb{Z}[X]/(X^N-1).\qquad(*)$$

We next "lift" $g_1$ to an inverse of $f$ modulo $4$ as follows. Multiplying both sides of $(*)$ by $1-2r_1(x)$ gives $$f(x)g_1(x)(1-2r_1(x))=1-4r_1(x)^2.$$ The right hand side differs from $1$ by a multiple of four, so if we set $g_2(x)=g_1(x)(1-2r_1(x))$ (do the calculation in the ring $\Bbb{Z}[X]/(X^N-1)$), then $$ f(x)g_2(x)=1+4r_2(x)\in\Bbb{Z}[X]/(X^N-1).\qquad(**) $$ In other words, $g_2(x)$ works as an inverse of $f$ in the ring $R_2$ Furthermore, because $1-2r_1(x)\equiv1\pmod 2$ we get that $g_2\equiv g_1\pmod 2$ (that's why we call $g_2$ a lifting of $g_1$.

Next we multiply both sides of $(**)$ by $1-4r_2(X)$. Repeating the dose, I declare $g_3(x)=g_2(x)(1-4r_2(x))$ and as $$(1-4r_2(x))(1+4r_2(x))=1-16r_2(x)^2\equiv1\pmod{16}$$ we see that $g_3(x)$ is an inverse of $f$ modulo sixteen or, more precisely, in the ring $R_4$. Also $g_3\equiv g_2\pmod4$, so we are still lifting.

Next you get a polynomial $g_4$ that is congruent to $g_3$ modulo $16$, and an inverse of $f$ modulo $16^2$. In your example case $q$ was $32$ so you can stop here and reduce the coefficients of $g_4$ modulo $32$. If $q$ is a higher power of two you rinse and repeat as the necessity arises.

---

In a lifting process we first figure out the least significant bits of all the coefficients of the inverse (i.e. modulo $2$), then in the subsequent rounds of iteration we figure out the next (or a few next) bits, but the process must not disturb the already "frozen" less significant bits. This is a common technique in all $p$-adic algebra. We work modulo an increasing sequence of powers of a fixed prime $p$. The technique is actually related to several approximation techniques from the real side. That's because in the $p$-adic world the least significant (=units) bit is actually the boss term, and the rest of them are more or less just supporting cast of decreasing importance as the exponent goes up.

---

I show the above steps for your example (aided by Mathematica in those steps that you can hopefully do using Sage instead).

So $N=11$, $q=32$ and $f=-x^{10}+x^9+x^6-x^4+x^2+x-1$. First we calculate the inverse modulo $2$. I used Mathematica's command PolynomialExtendedGCD and got the same result you did, namely $$ g_1=1+x+x^5. $$ Then I calculate the product (pretending that the coefficients are usual integers) $$ fg_1=-1 + 2 x^2 + x^3 - x^4 - 2 x^5 + 2 x^6 + 2 x^7 + x^{14} - x^{15}. $$ We need to reduce that modulo $x^{11}-1$. Doing that gives $$ \begin{aligned} fg_1&\equiv-1 + 2 x^2 + 2 x^3 - 2 x^4 - 2 x^5 + 2 x^6 + 2 x^7\\ &=1+2(-1+x^2+x^3-x^4-x^5+x^6+x^7), \end{aligned} $$ so $$ r_1(x)=-1 + x^2 + x^3 - x^4 - x^5 + x^6 + x^7. $$ Therefore we can calculate $g_2=g_1(1-2r_1)$ first as a polynomial, then reduced modulo $x^{11}-1$: $$ \begin{aligned} g_2&=3 + 3 x - 2 x^2 - 4 x^3 + 7 x^5 - 6 x^7 - 4 x^8 + 2 x^9 + 2 x^{10} - 2 x^{11} - 2 x^{12}\\ &\equiv 1 + x - 2 x^2 - 4 x^3 + 7 x^5 - 6 x^7 - 4 x^8 + 2 x^9 + 2 x^{10}. \end{aligned} $$ As I promised, $g_2$ differs from $g_1$ only by a multiple of two. Next we need to calculate $fg_2$. Again first as polynomial and then modulo $x^{11}-1$ (you can probably combine these steps easily): $$ fg_2 \equiv 13 + 4 x + 4 x^3 - 12 x^4 - 16 x^5 + 12 x^6 + 24 x^7 - 4 x^8 - 24 x^9 - 4 x^{10}. $$ As promised, $g_2$ works as an inverse of $f$ modulo four because this product differs from $1$ by multiples of four only. We also read that $fg_2=1+4r_2$, where $$ r_2=3 + x + x^3 - 3 x^4 - 4 x^5 + 3 x^6 + 6 x^7 - x^8 - 6 x^9 - x^{10}. $$ Next we need to compute $g_3=g_2(1-4r_2)$ modulo $x^{11}-1$: $$ g_3\equiv -219 - 439 x + 54 x^2 + 464 x^3 + 132 x^4 - 273 x^5 - 192 x^6 - 10 x^7 + 36 x^8 + 210 x^9 + 222 x^{10}. $$ At this point we see that modulo $x^{11}-1$ we have $$ fg_3\equiv881 + 624 x - 1264 x^2 - 1440 x^3 + 896 x^4 + 1712 x^5 - 176 x^6 - 1184 x^7 - 304 x^8 + 112 x^9 + 128 x^{10}. $$ As promised the product is $\equiv1\pmod{16}$, but not yet modulo $q=32$. However, the numbers are becoming progressively kludgier (my own fault because I chose to work in $\Bbb{Z}[x]/(x^{11}-1)$ instead of modulo $32$). Anyway, you see that my $g_3$ differs from your target answer by multiples of sixteen only, so the next round will take you there. Leaving that to you!