计算多项式逆的算法

我为拥有NTRU的安全创新部门工作，所以很高兴看到这种兴趣。

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

师：

输入是a和b，两个多项式，其中b为N-1级，b_N是b的前导系数。输出为q和r，使得a = q * b +
r且deg（r）<deg（b）。r_d表示度数为r的r系数，即r的前导系数。

a)  Set r := a and q := 0b)  Set u := (b_N)^–1 mod pc)  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 + vd)  Return q, r

在此，r_d是度d的r的系数。

扩展的欧几里得算法：

a)  If b = 0 then return (1, 0, a)b)  Set u := 1c)  Set d := a d)  Set v1 := 0e)  Set v3 := bf)  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 := t3g)  Set v := (d – a × u)/b  [This division is exact, i.e., the remainder is 0]h)  Return (u, v, d)

Z_p逆，pa素数：

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) × uc)  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 = pc)  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 × nd)  Return b(X) mod M(X) with coefficients computed modulo p^e.

如果您要完全实施NTRU，则应该查看是否可以让您的机构购买1363.1，因为原始NTRU加密对于活动的攻击者而言并不安全，并且1363.1描述了解决此问题的消息处理技术。

（更新2013-04-18：感谢Sonel Sharam发现了先前版本中的一些错误）