从伪代码实现递归 (NTRUEncrypt)
作为我最后一年大学项目的一部分，我需要实施 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 行：
int z[] = PolyMult(a1,b1,c1,n1,N);
我在第 16 行之前初始化了数组 a1,b1,c1，然后将它们传递给 PolyMult 本身（递归从这里 我的问题是：存储在数组 z[] 中的多项式何时会在程序中再次使用，我从伪代码中看不到任何迹象表明它将再次使用，但如果数组 z[]程序中不再使用，第 16 行和递归一起有什么意义？我应该如何实现第 16-18 行？
那么重复一下，何时以及如何在程序中再次使用数组 z 中存储的多项式？我应该如何实施第 16-18 行？
如需更深入的了解，可以在本文第 3 页找到伪代码的完整描述：http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在伪代码中，通过将结果存储到作为参数给出的
a[]数组中来“返回”结果。PolyMult(a1, b1, c1, n1, N)将其结果存储在a1[]中。这种乘法技术就是应用于多项式的 Karatsuba 乘法（这使得它变得更加容易，因为多项式中没有进位）。请参阅这篇维基百科文章以获取指示。
就我个人而言，我认为仅从数学角度理解比遵循伪代码更容易理解。
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 ina1[].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.
我在 NTRU 工作，所以我很高兴看到这种兴趣。
我不确定您正在使用什么参数集，但对于很多 NTRU 参数集，我们发现实施 Karatsuba 所涉及的开销是不值得的。假设您要将 A 和 B 相乘。对于 NTRUEncrypt 卷积运算，所涉及的多项式之一始终是二元或三元。假设这是 A。那么结果中的每个系数都是以下子集的总和
B 的系数。如果将 A 存储为非零系数索引数组，而不是将其存储为 1 和 0 的数组，并且如果 A 不太密集，则可以更快地处理该数组指数比做唐叶。代码也更小更简单。
请问你在哪所大学就读呢？
I work for NTRU, so I'm pleased to see this interest.
I'm not sure what parameter set you're using, but for a lot of NTRU parameter sets we find that the overhead involved in implementing Karatsuba isn't worth it. Say you're multiplying A and B. For NTRUEncrypt convolution operations, one of the polynomials involved is always binary or trinary. Say that's A. Then each coefficient in the result is a sum of a subset of
the coefficients of B. If you store A as the array of indices of coefficients that are non-zero, rather than storing it as an array of 1s and 0s, and if A is not too dense, then it's quicker to work through the array of indices than to do Karatsuba. The code is smaller and simpler too.
May I ask what university you're studying at?