다항식 역전을 계산하기위한 NTRU 의사 코드
-
20-09-2019 - |
문제
누구든지 다음 의사 코드의 45 행을 구현하는 방법을 알려줄 수 있는지 궁금했습니다.
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
. 기본적으로 온도는 다항식이며 (배열로 표시되고 있음) V는 정수 (4 또는 8)이므로 정확히 무엇을 하는가 temp = 2-temp mod v
정상적인 언어와 동일합니까? 내 코드에서 해당 라인을 어떻게 구현해야합니까? 누군가 나에게 모범을 줄 수 있습니까?
위의 알고리즘은 ntruencrypt 키 생성을위한 역 다항식을 계산하기위한 것입니다. 의사 코드는 28 페이지에 있습니다 이 문서. 미리 감사드립니다.
해결책
온도의 각 항목에 대해, 온도 [i], 설정 온도 [i] = 2- 템프 [i] mod v.
이것은 내 응답의 "z_p^n의 역수"섹션에 해당해야합니다. 다항식의 역수를 계산하기위한 알고리즘.
내가 지금 살펴보면, 내 대답이 그 말을하지 않을 수 있다고 생각합니다. 따라서 P = 2에는 효과가 있지만 다른 것은 아닙니다.
제휴하지 않습니다 StackOverflow