算法用于计算多项式的逆 [英] Algorithm for computing the inverse of a polynomial

问题描述

我在寻找一种算法（或code）帮我计算逆多项式，我需要它的实施NTRUEncrypt。一种算法，是很容易理解的是我preFER，有伪codeS这样做，但他们是混乱而难以实施，而且我也不太懂，从伪code程序孤独。

I'm looking for an algorithm (or code) to help me compute the inverse a polynomial, I need it for implementing NTRUEncrypt. An algorithm that is easily understandable is what I prefer, there are pseudo-codes for doing this, but they are confusing and difficult to implement, furthermore I can not really understand the procedure from pseudo-code alone.

任何算法计算多项式的逆相对于截断多项式的环的？

Any algorithms for computing the inverse of a polynomial with respect to a ring of truncated polynomials?

推荐答案

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

I work for Security Innovation, which owns NTRU, so I'm glad to see this interest.

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

The IEEE standard 1363.1-2008 specifies how to implement NTRUEncrypt with the most current parameter sets. It gives the following specifications to invert polynomials:

师：

输入是a和b，两个多项式，其中b是N-1次和B_N是b的首项系数。输出是q和r使得= Q * B + r和度（r）的＆其中;度（b）中。 R_D表示的d r的系数，即r的领先系数。

Inputs are a and b, two polynomials, where b is of degree N-1 and b_N is the leading coefficient of b. Outputs are q and r such that a = q*b + r and deg(r) < deg(b). r_d denotes the coefficient of r of degree d, i.e. the leading coefficient of 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的系数。

Here, r_d is the coefficient of r of degree d.

扩展欧几里德算法：

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，第一个素数：

Inverse in Z_p, p a 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素，M（X）一个合适的多项式如X ^ N-1

Inverse in Z_p^e / (M(X), p a prime, M(X) a suitable polynomial such as 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描述信息处理技术来解决这个问题。

If you're doing a full implementation of NTRU you should see if you can get your institution to buy 1363.1, as raw NTRU encryption isn't secure against an active attacker and 1363.1 describes message processing techniques to fix that.

（更新2013年4月18日：由于SONEL公司Sharam为察觉的一些错误，在previous版）

(Update 2013-04-18: Thanks to Sonel Sharam for spotting some errors in the previous version)

这篇关于算法用于计算多项式的逆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！