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 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:

a)  Set r := a and q := 0
b)  Set u := bN^–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
d)  Else return FALSE

Inverse in Z_p^n, p a prime:

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 = 2
c)  While n <= e do
1)  b(X) = 2 × b(X) – a(X) × b(X)2   (mod M(X)), with coefficients computed modulo p^n
2)  Set n = 2 × n
g)  Return b(X) mod M(X) with coefficients computed modulo pe.

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.

Answer 2

Hey steve, thanks for your help, I'm running into more problems when implementing this inverse algorithm, I can not seem to get the right results, I just need to clarify a few parts of the algorithm with you.

Any chance I can contact you, an e-mail address or anything?