NTRU用于计算多项式反转的伪代码

我想知道是否有人可以告诉我如何实现以下伪代码的第45行。NTRU用于计算多项式反转的伪代码

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究竟与正常语言等价呢？我应该如何在我的代码中实现该行。有人能给我一个例子。

上述算法用于计算NTRUE加密密钥生成的逆多项式。伪码可在this document的第28页找到。在此先感谢。

来源

2010-03-17 Mohammad Sepahvand

我试图实施NTRUEncrypt也因为你已经做到了这一点，考虑到你存储系数的方法与我的非常相似，如果你能给我一个反函数的手，我真的很感激它。有机会我可以通过电子邮件与您联系？ – FljpFl0p 2012-05-11 20:56:35

非常感谢，我会尽我所能来实现这一点。我下载了你发布的文件，并正在处理它。未来几天可能会打扰你。 – FljpFl0p 2012-05-12 06:21:14

我给你发了一封电子邮件。只是想知道你是否收到了它，以防地址错误。 – FljpFl0p 2012-05-12 18:05:06

对于温度的每个条目，温度[I]中，设置温度[I] = 2-TEMP [I] MOD诉

这应该对应于我的响应的部分中的 “Z_p^n的逆”到Algorithm for computing the inverse of a polynomial。

正如我现在看到它，我认为我的答案可能不会做它所说的 - 它说“逆Z_p^n”，但它看起来更像Z_2^n中的逆。所以它应该适用于p = 2，但可能不适用于其他任何东西。

来源

2010-03-17 21:05:01

感谢很多威廉，只是另一个快速问题，在：2-temp [i] mod v，这个模适用于2-temp [i]而不是temp [i]，对吗？所以我应该计算（2-temp [i]）％2而不是2-（temp [i]％2）对不对？ – 2010-03-18 09:46:12

是的，没错。 – 2010-03-19 19:41:34

嘿威廉，我试图找到一个（X）模32的逆，运行多项式算法的前31行后，（X）= [ - 1,1,1,0，-1， 0,1,0,0,1，-1]我的程序返回：b（X）= [1,1,0,0,0,1]和c（X）= [0,0,0,0， 0,0,0,0,1,1]和k = 11;我已经从NTRU教程中知道，（X）mod 32的倒数是[5,9,6,16,4,15,16,22,20,18,30]，但是当我继续其余的代码我得到了不同的答案。我想知道你能否检查我在第31行之后获得的b（X）值是否正确？如果你能这样做，我会非常感激。谢谢。 – 2010-03-21 08:36:08

NTRU用于计算多项式反转的伪代码

回答

相关问题