用于计算多项式逆的 NTRU 伪代码 [英] NTRU Pseudo-code for computing Polynomial Inverses
问题描述
我想知道是否有人可以告诉我如何实现以下伪代码的第 45 行.
I was wondering if anyone could tell me how to implement line 45 of the following pseudo-code.
Require: the polynomial to invert a(x), N, and q.
1: k = 0
2: b = 1
3: c = 0
4: f = a
5: g = 0 {Steps 5-7 set g(x) = x^N - 1.}
6: g[0] = -1
7: g[N] = 1
8: loop
9: while f[0] = 0 do
10: for i = 1 to N do
11: f[i - 1] = f[i] {f(x) = f(x)/x}
12: c[N + 1 - i] = c[N - i] {c(x) = c(x) * x}
13: end for
14: f[N] = 0
15: c[0] = 0
16: k = k + 1
17: end while
18: if deg(f) = 0 then
19: goto Step 32
20: end if
21: if deg(f) < deg(g) then
22: temp = f {Exchange f and g}
23: f = g
24: g = temp
25: temp = b {Exchange b and c}
26: b = c
27: c = temp
28: end if
29: f = f XOR g
30: b = b XOR c
31: end loop
32: j = 0
33: k = k mod N
34: for i = N - 1 downto 0 do
35: j = i - k
36: if j < 0 then
37: j = j + N
38: end if
39: Fq[j] = b[i]
40: end for
41: v = 2
42: while v < q do
43: v = v * 2
44: StarMultiply(a; Fq; temp;N; v)
45: temp = 2 - temp mod v
46: StarMultiply(Fq; temp; Fq;N; v)
47: end while
48: for i = N - 1 downto 0 do
49: if Fq[i] < 0 then
50: Fq[i] = Fq[i] + q
51: end if
52: end for
53: {Inverse Poly Fq returns the inverse polynomial, Fq, through the argument list.}
函数StarMultiply 返回存储在变量temp 中的多项式(数组).基本上 temp 是一个多项式(我将它表示为一个数组)，而 v 是一个整数(比如 4 或 8)，那么 temp = 2-temp mod v 在普通语言中到底等于什么?我应该如何在我的代码中实现该行.谁能给我举个例子.
The function StarMultiply returns a polynomial (array) stored in the variable temp. Basically temp is a polynomial (I'm representing it as an array) and v is an integer (say 4 or 8), so what exactly does temp = 2-temp mod v equate to in normal language? How should i implement that line in my code. Can someone give me an example.
上述算法用于计算 NTRUEncrypt 密钥生成的逆多项式.伪代码可以在 本文件.提前致谢.
The above algorithm is for computing Inverse polynomials for NTRUEncrypt key generation. The pseudo-code can be found on page 28 of this document. Thanks in advance.
推荐答案
对于 temp, temp[i] 中的每个条目，设置 temp[i] = 2-temp[i] mod v.
For each entry in temp, temp[i], set temp[i] = 2-temp[i] mod v.
这应该对应于我对 计算多项式逆的算法.
当我现在看它时，我认为我的答案可能不像它所说的那样 - 它说Z_p^n 中的逆"，但它看起来更像是 Z_2^n 中的逆.所以它应该适用于 p=2，但可能不适用于其他任何东西.
As I look at it now, I think my answer may not do what it says -- it says "Inverse in Z_p^n" but it looks more like an inverse in Z_2^n. So it should work for p=2 but maybe not for anything else.
这篇关于用于计算多项式逆的 NTRU 伪代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
