Algorithm for computing the inverse of a polynomial

Question

I'm looking for an algorithm (or code) to help me compute the inverse a polynomial, I need it for implementing NTRUEncrypt. An algorithm that is easily understandable is what I prefer, there are pseudo-codes for doing this, but they are confusing and difficult to implement, furthermore I can not really understand the procedure from pseudo-code alone.

Any algorithms for computing the inverse of a polynomial with respect to a ring of truncated polynomials?

Answer 1

I work for Security Innovation, which owns NTRU, so I'm glad to see this interest.

The IEEE standard 1363.1-2008 specifies how to implement NTRUEncrypt with the most current parameter sets. It gives the following specifications to invert polynomials:

Division:

Inputs are a and b, two polynomials, where b is of degree N-1 and b_N is the leading coefficient of b. Outputs are q and r such that a = q*b + r and deg(r) < deg(b). r_d denotes the coefficient of r of degree d, i.e. the leading coefficient of r.

a)  Set r := a and q := 0
b)  Set u := (b_N)^–1 mod p
c)  While deg r >= N do
  1)    Set d := deg r(X)
  2)    Set v := u × r_d × X^(d–N)
  3)    Set r := r – v × b
  4)    Set q := q + v
d)  Return q, r

Here, r_d is the coefficient of r of degree d.

Extended Euclidean Algorithm:

a)  If b = 0 then return (1, 0, a)
b)  Set u := 1
c)  Set d := a 
d)  Set v1 := 0
e)  Set v3 := b
f)  While v3 ≠ 0 do
  1)    Use the division algorithm (6.3.3.1) to write d = v3 × q + t3 with deg t3 < deg v3
  2)    Set t1 := u – q × v1
  3)    Set u := v1
  4)    Set d := v3
  5)    Set v1 := t1
  6)    Set v3 := t3
g)  Set v := (d – a × u)/b  [This division is exact, i.e., the remainder is 0]
h)  Return (u, v, d)

Inverse in Z_p, p a prime:

a)  Run the Extended Euclidean Algorithm with input a and (X^N – 1).  Let (u, v, d) be the output, such that a × u + (X^N – 1) × v = d = GCD(a, (X^N – 1)).
b)  If deg d = 0, return b = d^–1 (mod p) × u
c)  Else return FALSE

Inverse in Z_p^e / (M(X), p a prime, M(X) a suitable polynomial such as X^N-1

a)  Use the Inversion Algorithmto compute a polynomial b(X) ε R[X] that gives an inverse of a(X) in (R/pR)[X]/(M(X)). Return FALSE if the inverse does not exist. [The Inversion Algorithm may be applied here because R/pR is a field, and so (R/pR)[X] is a Euclidean ring.]
b)  Set n = p
c)  While n <= e do
  1)    b(X) = p × b(X) – a(X) × b(X)^2   (mod M(X)), with coefficients computed modulo p^n
  2)    Set n = p × n
d)  Return b(X) mod M(X) with coefficients computed modulo p^e.

If you're doing a full implementation of NTRU you should see if you can get your institution to buy 1363.1, as raw NTRU encryption isn't secure against an active attacker and 1363.1 describes message processing techniques to fix that.

(Update 2013-04-18: Thanks to Sonel Sharam for spotting some errors in the previous version)