Given any algebraic ring R (a structure with addition, subtraction, and multiplication but not necessarily division) we can create another ring R[x] made from polynomials with coefficients taken from R. For example, the integers are a ring, usually written Z, and polynomials with integer coefficients from the ring Z[x].
One application of polynomial rings is the NTRU encryption algorithm, where we are working in Z[x]/(X^N−1) or with the related ring where the coefficients are taken modulo p, Z_p[x]/(X^N−1). These rings have an additional property: they are "quotient rings" where we have "divided" by a polynomial, in this case X^N - 1 for some fixed N. In practical terms, that acts like a modulus; we have shifted from polynomials to equivalence classes of polynomials, all of which differ by a factor of X^N-1, so adding or subtracting that polynomial has no effect.
The identity element of these rings is the constant polynomial 1. To find the inverse of a polynomial f(x), we want a solution to f(x)g(x) = 1 + (x^N−1)m(x). That is, f(x)g(x) ≡ 1 (mod x^N−1) . Using the Extended Euclidean Algorithm gives us a way to compute this, in the form
f(x)g(x)+(x^N−1)(−m(x))=1
by taking the greatest common divisor (GCD) of f(x) and x^N−1. Naturally if their GCD is not 1 then we have a problem, but since the input polynomial has degree strictly less than N and N is a prime in NTRU, the only case where the GCD is not 1 is the zero polynomial.
We can describe the EEA as a recurrence of the form
r_{k−2} = q_k * r_{k−1} + r_k
(that is, r_k is the remainder after division of the previous two elements in the sequence.)
s_k = s_{k−2} − q_k * s_{k−1}
t_k = t_{k−2} − q_k * t_{k−1}
Starting with
r_{−2}=x^N−1
r_{-1}=f
s_{−2}=1
s_{−1}=0
t_{−2}=0
t_{−1}=1
See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Because we’re doing polynomial division, the remainder has a smaller degree than the dividend polynomial rather than a smaller magnitude.
Let’s do an example. What is the inverse of x^2+1 in Z_3[x]/(x^5−1)?
First note that −1 ≡ 2 in Z_3. The first polynomial long division gives
x^5−1=(x^3+2x)(x^2+1)+(x+2)
Step 0: q_0=x^3+2x, r0=x+2
Dividing again, x^2+1=(x+1)(x+2)+2
Step 1: q_1=x+1, r_1=2
x+2=(2x+1)2+0
Step 2: q_2=2x+1, r_2=0
We only need the value for t (the value for s is the factor associated with x^N−1.) The EEA actually gives us the negative of the value we want, that is, (x^N−1)(s_k)+(x^2+1)(t_k)=1, so we need −t_k. (This is easy to fix, just check whether you get 1 or -1 when multiplying the inverse by the original polynomial.) Using the formula for t_k above, we get
t_0 = 0 − q_0 * 1 = 2x^3+x
t_1 = 1 − q_1 * t_0 = 1−(x+1)(2^x3+x)= x^4+x^3+2x^2+2x+1
So our inverse is 2x^4+2x^3+x^2+x+2. Checking our math:
(2x^4+2x^3+x^2+x+2)(x^2+1)
=2x^6+2x^5+3x^4+3x^3+3x^2+x+2
≡2x^6+2x^5+x+2
≡2x^6+x+1 (we can freely add or subtract x^5−1 because it’s the modulus.)
≡1 (adding a multiple of the modulus x(x^5–1))
Originally answered on Quora: https://www.quora.com/How-do-I-calculate-the-multiplicative-inverse-for-polynomial-in-ntru-encryption/answer/Mark-Gritter