다항식의 역함수를 계산하는 알고리즘

Question

역 다항식을 계산하는 데 도움이되는 알고리즘 (또는 코드)을 찾고 있는데, NTRUEncrypt를 구현하는 데 필요합니다. 쉽게 이해할 수있는 알고리즘은 내가 선호하는 것입니다. 이렇게하는 의사 코드가 있지만 구현하기가 어렵고 혼란스럽고 의사 코드만으로는 그 절차를 이해할 수 없습니다.

ring of truncated polynomials에 관한 다항식의 역행렬을 계산하는 알고리즘은 무엇입니까?

Answer 1

저는 NTRU를 소유 한 Security Innovation에서 일하므로이 관심사를 보게되어 기쁩니다.

IEEE 표준 1363.1-2008은 최신 매개 변수 집합을 사용하여 NTRUEncrypt를 구현하는 방법을 지정합니다. 이 다항식 반전 아래 사양을 제공한다 :

는

등급 :

입력은 B가도 N-1이고 A와 B 두 다항식이며 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 : Z_p^E/(M (X에

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 

역), 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. 

당신은 b에 교육 기관을 얻을 수있는 경우에 당신이 볼 수 NTRU의 전체 구현을하고 있다면 uy 1363.1, 원시 NTRU 암호화는 활성 공격자에 대해 안전하지 않으므로 1363.1에서는이를 해결하기위한 메시지 처리 기술을 설명합니다.

(업데이트 : 2013-04-18 : 이전 버전의 일부 오류를 찾아 주셔서 감사합니다.)