Implementing Recursion from psuedo-code (NTRUEncrypt)

Question

Hello again everyone. I am required to implement the NTRU Public Key Cyptosystem as part of my final year University project. I'm trying to implement an algorithm that multiplies long polynomials via recursion, however I'm quite bogged down in trying to understand the pseudo-code.

Algorithm PolyMult(c, b, a, n, N)
Require: N, n, and the polynomial operands, b and c.
PolyMult returns the product polynomial a through the argument list
PolyMult(a,b,c,n,N)
{
1. if(...)
2. {
3.    ...
4.    ...
5.    ...
6.    ...
7. }
8. else
9. {
10.   n1 = n/2;
11.   n2 = n-n1;
12.   b = b1+b2*X^(n1);
13.   c = c1+c2*X^(n1);
14.   B = b1+b2;
15.   C = c1+c2;
16.   PolyMult(a1,b1,c1,n1,N);// a1 = b1*c1
17.   PolyMult(a2,b2,c2,n2,N);// a2=b2*c2
18.   PolyMult(a3,B,C,n2,N);// a3 = B*C=(b1+b2)*(c1+c2)
19.   a = a1 + (a3-a1-a2)*X^(n1) + a2*X^(2*n1);
20.}
}

Note that N, n, n1 and n2 are all type int. a,a1,a2,b,b1,b2,c,c1,c2,B,C are all polynomials and are represented as arrays.

On lines 16, 17 and 18, the function PolyMult is called with arguments of a1,b1,c1,n1,N then a2,b2,c2,n2,N and finally a3,B,C,n2,N respectively. I have initialised the arrays a1,b1,c1 before line 16, then I pass those into PolyMult itself (recursion starts here!) and return an answer and store it in some temporary array, say for example I implement line 16 as follows:

int z[] = PolyMult(a1,b1,c1,n1,N);

Now my question is: when will the polynomial stored in array z[] be used again in the program, I see no indication that it will be used again from the pseudo-code, but if array z[] is not used again in the program, what is the point of line 16 and recursion all together? How should I implement lines 16-18?

So to repeat, when and how will the polynomial stored in array z be used again in the program? And how should I go about implementing lines 16-18?

For more insight a full description of the pseudo-code can be found on page 3 of this article: http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf.

I would be extremely grateful for any guidance (this is for my final year University project!).

Thanks again.

Answer 1

In the pseudo-code, the result is "returned" by storing it into the a[] array, which is given as parameter. PolyMult(a1, b1, c1, n1, N) stores its result in a1[].

That multiplication technique is simply the Karatsuba multiplication, applied on polynomials (which makes it even easier, because there is no carry in polynomials). See this Wikipedia article for pointers.

Personally, I think that it is easier to understand from the math alone, rather than by following pseudo-code.

Answer 2

I work for NTRU, so I'm pleased to see this interest.

I'm not sure what parameter set you're using, but for a lot of NTRU parameter sets we find that the overhead involved in implementing Karatsuba isn't worth it. Say you're multiplying A and B. For NTRUEncrypt convolution operations, one of the polynomials involved is always binary or trinary. Say that's A. Then each coefficient in the result is a sum of a subset of the coefficients of B. If you store A as the array of indices of coefficients that are non-zero, rather than storing it as an array of 1s and 0s, and if A is not too dense, then it's quicker to work through the array of indices than to do Karatsuba. The code is smaller and simpler too.

May I ask what university you're studying at?