Implementing Recursion from pseudo-code (NTRUEncrypt)
cryptography, java, polynomial-math, recursion
Solution
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.
Problem
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.