从伪码(NTRUEncrypt)实现递归

Question

我被要求实现NTRU公开密钥系统作为我的最后一年大学项目的一部分。我试图实现一种算法，通过递归将长多项式相乘，但是我很难理解伪码。

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.}
}

注意，N，n，n1和n2都是int类型。a，a1，a2，b，b1，b2，c，c1，c2，B，C都是多项式，表示为数组。

在第16、17和18行中，函数PolyMult分别使用a1、b1、c1、n1、N然后a2、b2、c2、n2、N和最后的a3、B、C、n2、N等参数调用。我在第16行之前初始化了数组a1、b1、c1，然后将它们传递到PolyMult本身(递归从这里开始！)并返回一个答案并将其存储在某个临时数组中，例如，我实现了第16行，如下所示：

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

现在我的问题是：当程序中再次使用存储在数组z[]中的多项式时，没有迹象表明它将从伪代码中再次使用，但是如果程序中不再使用数组z[]，那么第16行和递归在一起的意义是什么？我应该如何实现第16-18行？

因此，重复一遍，何时以及如何在程序中再次使用存储在数组z中的多项式？我应该如何实现第16-18行呢？

要获得更多了解，可以在本文的第3页：http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf中找到对伪代码的完整描述。

Answer 1

在伪代码中，结果通过将其存储到作为参数的a[]数组中“返回”。PolyMult(a1, b1, c1, n1, N)将其结果存储在a1[]中。

这种乘法技术就是对多项式应用的Karatsuba乘法(这使得它更容易，因为多项式中没有进位)。有关指针，请参见这篇维基百科文章。

就我个人而言，我认为它更容易理解从数学本身，而不是遵循伪代码。

Answer 2

我在NTRU工作，所以我很高兴看到这种兴趣。

我不知道您使用的是哪个参数集，但是对于很多NTRU参数集，我们发现实现Karatsuba所涉及的开销不值得。假设你把A和B相乘，对于NTRUEncrypt卷积运算，所涉及的多项式之一总是二进制或三进制。假设这是A，那么结果中的每个系数都是B的系数子集的和。如果你将A存储为非零系数的索引数组，而不是将它存储为1s和0的数组，如果A不太密集，那么处理指数数组比做Karatsuba要快。代码也更小更简单。

请问你在哪所大学学习？