java - 从伪代码(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[] 中的多项式什么时候会在程序中再次使用，我从伪代码中看不到它会再次使用的迹象，但是如果array 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 乘法(这使得它更容易，因为多项式中没有进位)。参见 this Wikipedia article求指点。

就我个人而言，我认为仅从数学上理解比遵循伪代码更容易理解。