计算多项式倒数的算法

Question

我正在寻找一种算法（或代码）来帮助我计算多项式的逆，我需要它来实现 NTRUEncrypt。我更喜欢易于理解的算法，有伪代码可以做到这一点，但它们很混乱且难以实现，而且我无法仅从伪代码真正理解该过程。

用于计算关于截断多项式环的多项式的逆的任何算法？

Answer 1

我在 Security Innovation 工作，该公司拥有 NTRU，所以我很高兴看到这种兴趣。

IEEE 标准 1363.1-2008 指定如何使用最新的参数集实施 NTRUEncrypt。它给出了以下规范来反转多项式：

除法：

输入是 a 和 b，两个多项式，其中 b 的次数为 N-1，b_N 是 b 的首项系数。输出为 q 和 r，使得 a = q*b + r 且 deg(r) <度(b)。 r_d表示r的d次系数，即r的首项系数。

a)  Set r := a and q := 0
b)  Set u := (b_N)^–1 mod p
c)  While deg r >= N do
  1)    Set d := deg r(X)
  2)    Set v := u × r_d × X^(d–N)
  3)    Set r := r – v × b
  4)    Set q := q + v
d)  Return q, r

这里，r_d是d次r的系数。

扩展欧几里德算法：

a)  If b = 0 then return (1, 0, a)
b)  Set u := 1
c)  Set d := a 
d)  Set v1 := 0
e)  Set v3 := b
f)  While v3 ≠ 0 do
  1)    Use the division algorithm (6.3.3.1) to write d = v3 × q + t3 with deg t3 < deg v3
  2)    Set t1 := u – q × v1
  3)    Set u := v1
  4)    Set d := v3
  5)    Set v1 := t1
  6)    Set v3 := t3
g)  Set v := (d – a × u)/b  [This division is exact, i.e., the remainder is 0]
h)  Return (u, v, d)

Z_p 的逆，pa prime：

a)  Run the Extended Euclidean Algorithm with input a and (X^N – 1).  Let (u, v, d) be the output, such that a × u + (X^N – 1) × v = d = GCD(a, (X^N – 1)).
b)  If deg d = 0, return b = d^–1 (mod p) × u
c)  Else return FALSE

Z_p^e 的逆 / (M(X), pa prime, M(X) 一个合适的多项式，例如 X^N-1

a)  Use the Inversion Algorithmto compute a polynomial b(X) ε R[X] that gives an inverse of a(X) in (R/pR)[X]/(M(X)). Return FALSE if the inverse does not exist. [The Inversion Algorithm may be applied here because R/pR is a field, and so (R/pR)[X] is a Euclidean ring.]
b)  Set n = p
c)  While n <= e do
  1)    b(X) = p × b(X) – a(X) × b(X)^2   (mod M(X)), with coefficients computed modulo p^n
  2)    Set n = p × n
d)  Return b(X) mod M(X) with coefficients computed modulo p^e.

如果您正在完整实现 NTRU您应该看看是否可以让您的机构购买 1363.1，因为原始 NTRU 加密对于主动攻击者来说并不安全，并且 1363.1 描述了解决该问题的消息处理技术

（2013 年 4 月 18 日更新：感谢 Sonel Sharam 发现了一些问题。之前版本有错误）