Algoritmo para calcular la inversa de un polinomio

Question

Estoy buscando un algoritmo (o código) que me ayude a calcular el inverso un polinomio, lo necesito para implementar NTRUEncrypt. Un algoritmo que es fácilmente comprensible es lo que prefiero, hay pseudo-códigos para hacer esto, pero son confusas y difíciles de aplicar, además, realmente no puedo entender el procedimiento de pseudo-código sola.

Cualquier algoritmos para el cálculo de la inversa de un polinomio con respecto a un anillo de polinomios truncadas

Answer 1

Yo trabajo para la Seguridad Innovación, que posee NTRU, así que estoy contento de ver este interés.

El estándar IEEE 1363,1-2008 especifica cómo implementar NTRUEncrypt con los conjuntos de parámetros más actuales. Se da las siguientes especificaciones para invertir polinomios:

División:

Las entradas son a y b, dos polinomios, donde b es de grado N-1 y b_n es el coeficiente principal de b. Los resultados son los q y r tales que a = q * b + r y DEG (r) <° (b). r_d designa el coeficiente de r de grado d, es decir, el coeficiente 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

Aquí, r_d es el coeficiente de r de grado d.

extendido de Euclides Algoritmo:

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)

Invertir en Z_p, p un número primo:

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 en Z_p ^ e / (M (X), p un número primo, M (X) un polinomio adecuado tal como 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 estás haciendo una implementación completa de NTRU usted debe ver si usted puede conseguir su institución para comprar 1363.1, como el cifrado NTRU prima no es segura contra un atacante activo y 1363.1 describe las técnicas de procesamiento de mensajes de arreglar eso.

(Actualización 18/04/2013: Gracias a Sonel Sharam para detectar algunos errores en la versión anterior)