다항식의 역수를 계산하기위한 알고리즘

Question

역수를 계산하는 데 도움이되는 알고리즘 (또는 코드)을 찾고 있습니다. ntruencrypt 구현이 필요합니다. 쉽게 이해할 수있는 알고리즘은 내가 선호하는 것입니다.이 작업을 수행하기위한 의사 코드가 있지만 혼란스럽고 구현하기가 어렵습니다.

에 대한 다항식의 역수를 계산하기위한 모든 알고리즘 잘린 다항식의 고리?

Answer 1

NTRU를 소유 한 보안 혁신을 위해 일하고 있기 때문에이 관심을 보게되어 기쁩니다.

IEEE 표준 1363.1-2008은 최신 매개 변수 세트로 NTruencrypt를 구현하는 방법을 지정합니다. 다항식을 반전하기 위해 다음과 같은 사양을 제공합니다.

분할:

입력은 A와 B, 2 개의 다항식이며, 여기서 B는 N-1도이고 B_N은 B의 주요 계수입니다. 출력은 q 및 r이며 a = q*b + r 및 deg (r) <deg (b)입니다. R_D는 D의 R의 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)

PA 프라임 Z_P의 역수 :

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를 완전히 구현하고 있다면 RAW NTRU 암호화가 활성 공격자에 대해 안전하지 않으며 1363.1이이를 해결하기위한 메시지 처리 기술을 설명하기 때문에 기관이 1363.1을 구매할 수 있는지 확인해야합니다.

(2013-04-18 업데이트 : 이전 버전에서 일부 오류를 발견 한 Sonel Sharam에게 감사합니다)