NTRU Псевдокод для вычисления полиномиальных инверсий

Question

Мне было интересно, может ли кто-нибудь рассказать мне, как реализовать строку 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. В принципе temp является полиномом (я представляю его как массив), а v - целое число (скажем, 4 или 8), так что же делает temp = 2-temp mod v на нормальном языке? Как мне реализовать эту строку в моем коде. Может ли кто-нибудь дать мне пример.

Вышеупомянутый алгоритм предназначен для вычисления инверсных полиномов для генерации ключей NTRUEncrypt. Псевдокод можно найти на странице 28 из this document. Спасибо заранее.

Answer 1

Для каждой записи в темп, темп [я], установите темп [я] = 2-ТЕМП [я] мод ст.

Это должно соответствовать «Inverse в Z_p^п» части моего ответа до Algorithm for computing the inverse of a polynomial.

Поскольку я смотрю на это сейчас, я думаю, что мой ответ может не делать то, что он говорит, - он говорит «Обратный в Z_p^n», но он больше похож на обратный в Z_2^n. Поэтому он должен работать на p = 2, но, возможно, не на что-то еще.