NTRU pseudo-código para calcular inversas polinómicas

Question

Me preguntaba si alguien podría decirme cómo poner en práctica la línea 45 de la siguiente pseudo-código.

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.}

El StarMultiply función devuelve un polinomio (array) almacenado en el temp variable. Básicamente Temp es un polinomio (Estoy representando como una matriz) y v es un número entero (por ejemplo 4 u 8), por lo que lo hace exactamente temp = 2-temp mod v equiparan en el lenguaje normal? ¿Cómo debo poner en práctica esa línea en mi código. Alguien me puede dar un ejemplo.

El algoritmo anterior es para el cálculo de polinomios inversa para la generación de claves NTRUEncrypt. El pseudo-código se puede encontrar en la página 28 de este documento. Gracias de antemano.

Answer 1

Para cada entrada en temp, temp [i], ajuste temp [i] = 2-temp [i] v mod.

Esto debería corresponder a la "inversa en Z_p ^ n" sección de mi respuesta a algoritmo para calcular la inversa de una polinomio.

Como yo lo veo ahora, creo que mi respuesta no puede hacer lo que dice - que dice "inverso en Z_p ^ n", pero se parece más a una inversa en Z_2 ^ n. Así que debería funcionar para p = 2, pero quizás no para cualquier otra cosa.