7

逆多項式を計算するのに役立つアルゴリズム（またはコード）を探しています。NTRUEncryptを実装するために必要です。簡単に理解できるアルゴリズムが私が好むものです。これを行うための擬似コードがありますが、それらは混乱し、実装が困難です。さらに、擬似コードだけから手順を理解することはできません。

切り捨てられた多項式のリングに関して多項式の逆数を計算するためのアルゴリズムはありますか？

4

1 に答える 1

12

私はNTRUを所有するSecurityInnovationで働いているので、この関心を見てうれしく思います。

IEEE標準1363.1-2008は、最新のパラメータセットを使用してNTRUEncryptを実装する方法を指定しています。多項式を反転するために、次の仕様が与えられます。

分割：

入力はaとb、2つの多項式です。ここで、bは次数N-1であり、b_Nはbの主要な係数です。出力は、a = q * b + rおよびdeg（r）<deg（b）となるqおよびrです。r_dは、次数dのrの係数、つまり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プライム：

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などの適切な多項式

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-04-18：以前のバージョンでいくつかのエラーを発見してくれたSonel Sharamに感謝します）

于 2010-03-11T16:01:10.163 に答える