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?

Lurdan

Which inverse? Do you want the inverse function, to solve (i.e. factorise) polynomials, or do you want to find their multiplicative inverses in the field formed as the quotient of the polynomials over some base field, and an irreducible polynomial? NTRU stands for "Number Theorists R Us", IIRC, so it's difficult to intuit just what mathematics is required. en.wikipedia.org/wiki/NTRUEncrypt says "both encryption and decryption use only simple polynomial multiplication", so that article didn't tell me what you mean either. Whatever is needed, this could be a MathOverflow question. – Chamomile

here ntru.com/cryptolab/tutorial_algebra.htm#three – Lurdan

Gotcha. It's more like the second thing I said, although not actually the field I described but a slightly different ring (not all inverses exist). If you read NTRU technical note 14, there's an explanation at the end, after the pseudo-code, of "why it works". It's kind of like inverting a matrix by row-reduction, in the sense that you apply a bunch of transforms until you get 1, then the inverse is all the inverses of those transforms multiplied together. That's what the pseudo-code is doing. But I don't claim to have fully digested note 14, I just skimmed it. – Chamomile

I don't really understand much of note 14, and the mathematics behind all this is too much for me to grasp, i'm trying to do a basic implementation of NTRU but I can't get the inverse polynomial generator for public key creation to work, it's so frustrating...and the pseudocode is even more confusing....thanks anyways. – Lurdan

Note also that it's a very specific algorithm to (1) the particular ring that NTRUEncrypt uses, and (2) the particular prime fields (2 and 3) that it uses. Generic answers to "how do I invert a polynomial" aren't necessarily applicable, because you get a different answer inverting polynomials in different fields (or rings, in this case). – Chamomile

In that case go for carefully copying the pseudo-code, operation by operation. When they say things like, f(X):=a(X), they mean that f is a variable in your routine, a is an input to the function, and the type of both those things is "polynomial". f(X)/X means for instance x^2 + x + 0 -> x + 1. The other tricky part is when you finally get your answer, you have to reduce it mod X^N-1. – Chamomile

It sounds like you perhaps need a little more background in abstract algebra (finite fields, groups, rings, etc.) in order to understand the algorithms you've seen sketched out in pseudocode. Without that background, it's hard to imagine what an "easily understandable" explanation might look like. – Popover

I should add that I have a master's degree in maths, so Note 14 is essentially stuff I've seen, if not remembered. The quotient ring is 2nd or 3rd year undergraduate stuff where I studied, which was Oxford. Note that at Oxford you specialise as soon as you arrive, so at the start of the 2nd year you've spent a year doing nothing but mathematics courses. This isn't something you'll fully pick up the theory of overnight, but if you can learn the base concepts of multiplying and dividing polynomials you can implement the algorithm. The abstract algebra helps, but isn't necessary. – Chamomile

Oh, and write a unit test for your function. You should be able to multiply the output by the input, reduce the coefficients modulo 2, reduce the resulting polynomial modulo X^N-1, and get the polynomial 1 (that is, all coefficients 0 except the last). – Chamomile

Thanks a lot steve, I'm trying to implement the pseudo-code line by line very carefully, there is an extended pseudo-code that's written more clearly here: wpi.edu/Pubs/ETD/Available/etd-0430102-111906/unrestricted/… on page 27, I'm coding that carefully and i'm testing it with some sample answers given by NTRU, I think i'm also getting held back in understanding the pseudo-code, in my code I gave a fixed length and set of values to the polynomial f, and the infinite loop on 8-31 never ended, thanks for pointing out that f is a variable. Any more tricks to watch out for? – Lurdan

Nothing springs to mind. Everything listed in "Step 1: Initialization" is a variable, and is modified somewhere. You should see f and g get smaller and smaller (in terms of their highest non-zero coefficient), while b, c and k in effect record what you did to f and g. Once f is as small as it can get (1) in step 5, the stuff you've "built up" in b and k gives you the inverse, you just have to put that information together. As an implementation detail, if you're storing a polynomial as an array of coefficients, then multiplying or dividing by x just means shift everything along one place. – Chamomile

Yea I'm using arrays, thanks again, I noticed f and g should be getting smaller but they were not when i was running it since I had assigned fixed values to f, therefore my infinite loop would never end and my program ran forever since the break; on step 19 was never reached since the precondition (if deg(f)==0) was never met. Thanks for your help, greatly appreciated. – Lurdan

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)

Bernina

If I might resurrect this question, is there any advice you can give if I my implementation keeps failing because b_N ^-1 mod p does not exists? Specifically, something like 2044 ^-1 mod 2048 will come up which causes the algorithm to fail. I just restart with a new f but it fails indefinitely. – Vara

You know what, it was the last psuedo-code section computing things mod p instead of mod p^e and then raising it that fixed it. Gunna take some time to grok that, though. – Vara

In the algorithm to compute the inverse in Z_p^e / (M(X)) the point c ) 2) seems to be wrong. This should be n = n + 1 instead of n = p * n, since n is the exponent of p. I just tested this with the example given on Wikipedia and it works with n = n + 1 but not with n = p * n. – Liuka

If this is right, line b) could be also wrong and should be n = 2. For p = 2 it makes no difference. – Liuka

@William, if you are still active on Stack Overflow then please contact me at noloader, gmail account. I'm looking for a NTRU specialist to help/advise me with an open source implementation. – Naturopathy