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 متغير. في الأساس مؤقت هو متعدد الحدود (أنا يمثلون أنها مجموعة) والخامس هو عدد صحيح (ويقول 4 أو 8)، يفعل ذلك بالضبط ما temp = 2-temp mod v يعادل في اللغة العادية؟ كيف يجب أن تنفيذ هذا الخط في قانون بلدي. يمكن للشخص أن تعطيني مثالا على ذلك.

والخوارزمية أعلاه لحساب متعددو الحدود العكسية لNTRUEncrypt الجيل الرئيسيين. يمكن العثور على رمز الزائفة على الصفحة 28 من <لأ href = "http://www.wpi.edu/Pubs/ETD/Available/etd-0430102-111906/unrestricted/corourke.pdf" يختلط = "noreferrer نوفولو" > هذه الوثيقة . يرجع الفضل في ذلك مسبقا.

Answer 1

للكل إدخال في درجة الحرارة، درجة الحرارة [أنا]، درجة الحرارة تعيين [ط] = 2-درجة الحرارة [أنا] وزارة الدفاع ضد

وهذا يجب أن تتوافق مع "معكوس في Z_p ^ ن" من ردي على <لأ href = "https://stackoverflow.com/questions/2421409/algorithm-for-computing-the-inverse-of-a -polynomial / 2426520 # 2426520 "> خوارزمية لحساب معكوس من متعدد الحدود.

وكما ننظر إليها الآن، وأعتقد جوابي قد لا تفعل ما تقول - تقول "معكوس في Z_p ^ ن" ولكن يبدو أشبه معكوس في Z_2 ^ ن. لذلك يجب أن تعمل لص = 2 ولكن ربما ليس لأي شيء آخر.