4

作为我最后一年大学项目的一部分，我需要实施 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。

4

2 回答 2

3

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

该乘法技术只是应用于多项式的 Karatsuba 乘法（这使得它更容易，因为多项式中没有进位）。有关指针，请参阅此 Wikipedia 文章。

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

于 2010-03-06T22:24:18.903 回答
0

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

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

请问你在哪所大学读书？

于 2010-03-08T20:26:59.257 回答