作为我最后一年大学项目的一部分，我需要实现 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 。
最佳答案
在伪代码中，通过将结果存储到 a[] 数组中来“返回”结果，该数组作为参数给出。 PolyMult(a1, b1, c1, n1, N) 将其结果存储在 a1[] 中。
该乘法技术只是应用于多项式的 Karatsuba 乘法(这使得它更容易，因为多项式中没有进位)。有关指针，请参阅 this Wikipedia article。
就个人而言，我认为仅从数学上理解比通过伪代码更容易理解。
关于java - 从伪代码实现递归 (NTRUEncrypt)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2393649/