Implementing recursion from pseudo-code (NTRUEncrypt)

Question

I need to implement the Cyptosystem NTRU public key as part of my university project last year. I am trying to implement an algorithm that multiplies long polynomials through recursion, however I am pretty bogged down in an attempt to understand the pseudocode.

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 int types. a, a1, a2, b, b1, b2, c, c1, c2, B, C are all polynomials and are presented as arrays.

On lines 16, 17 and 18, the PolyMult function is called with arguments a1, b1, c1, n1, N, then a2, b2, c2, n2, N and finally a3, B, C, n2, N, respectively, I initialized the arrays a1, b1, c1 before line 16, then pass them to PolyMult (recursion starts here!) and returns the response and save it in some temporary array, for example, I implement line 16 as follows:

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

Now my question : when the polynomial stored in the z [] array is 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 to implement lines 16-18?

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

For more information, a full description of the pseudocode can be found on page 3 of this article: http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf .

Answer 1

In pseudocode, the result is "returned", storing it in the array a[] , which is specified as a parameter. PolyMult(a1, b1, c1, n1, N) stores the result in a1[] .

This multiplication method is just the Karatsuba multiplication applied to polynomials (which makes it even easier because there is no transfer in the polynomials). See this Wikipedia article for pointers.

Personally, I believe that this is easier to understand only in mathematics, and not in pseudo-code.

Answer 2

I work at NTRU, so I'm glad to see this interest.

I'm not sure which parameter you are using, but for many sets of NTRU parameters, we find that the overhead associated with implementing Karatsuba is not worth it. Say you multiply A and B. For NTRUEncrypt convolution operations, one of the polynomials involved is always binary or trinial. Let's say that A. Then each coefficient as a result is the sum of a subset of the coefficients B. If you save A as an array of non-zero coefficient indices, instead of storing it as an array of 1s and 0s, and if A is not too dense , then it works faster through an array of indexes than doing Karatsuba. The code is smaller and simpler.

May I ask what university you study at?