Algorithme de calcul de l'inverse d'un polynôme

Question

Je cherche un algorithme (ou code) pour m'aider à calculer l'inverse d'un polynôme, j'en ai besoin pour l'implémentation de NTRUEncrypt. Un algorithme qui est facilement compréhensible est ce que je préfère, il y a des pseudo-codes pour le faire, mais ils sont déroutants et difficiles à implémenter, en outre je ne peux pas vraiment comprendre la procédure du pseudo-code seul.

Des algorithmes pour calculer l'inverse d'un polynôme par rapport à un ring of truncated polynomials?

Answer 1

Je travaille pour Security Innovation, qui possède NTRU, donc je suis heureux de voir cet intérêt.

La norme IEEE 1363.1-2008 spécifie comment implémenter NTRUEncrypt avec les jeux de paramètres les plus courants. Il donne les spécifications suivantes pour inverser polynômes:

Division:

sont entrées a et b, deux polynômes, où b est de degré N-1 et b_n est le premier coefficient de b. Les résultats sont q et r tels que a = q * b + r et deg (r) < deg (b). r_d désigne le coefficient de r de degré d, c'est-à-dire le coefficient principal de 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 

Ici, r_d est le coefficient de r de degré d.

Euclide étendu Algorithme:

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) 

inverse dans Z_p, pa Premier:

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 

inverse dans Z_p^e/(M (X), pa premier, M (X) a adapté polynôme tel que 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. 

Si vous faites une mise en œuvre complète de NTRU vous devriez voir si vous pouvez obtenir votre institution b uy 1363.1, car le cryptage NTRU brut n'est pas sécurisé contre un attaquant actif et 1363.1 décrit les techniques de traitement des messages pour résoudre ce problème.

(Mise à jour 18/04/2013: Merci à SONEL Sharam pour repérer des erreurs dans la version précédente)