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

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

2 голосов
/ 17 марта 2010

Мне было интересно, может кто-нибудь сказать мне, как реализовать строку 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 этого документа . Заранее спасибо.

1 Ответ

1 голос
/ 18 марта 2010

Для каждой записи в temp, temp [i], установите temp [i] = 2-temp [i] mod v.

Это должно соответствовать разделу «Обратное в Z_p ^ n» моего ответа на Алгоритм вычисления обратного полинома .

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

...