Código binario de Goppa

En matemáticas y ciencias de la computación , el código binario Goppa es un código de corrección de errores que pertenece a la clase de códigos Goppa generales descritos originalmente por Valerii Denisovich Goppa , pero la estructura binaria le otorga varias ventajas matemáticas sobre las variantes no binarias, y también proporciona un mejor ajuste para el uso común en computadoras y telecomunicaciones. Los códigos binarios Goppa tienen propiedades interesantes adecuadas para la criptografía en criptosistemas tipo McEliece y configuraciones similares.

Un código Goppa binario irreducible se define mediante un polinomio de grado sobre un campo finito sin raíces repetidas y una secuencia de elementos distintos de que no son raíces de . ${\estilo de visualización g(x)}$${\estilo de visualización t}$ ${\displaystyle GF(2^{m})}$${\displaystyle L_{1},...,L_{n}}$${\estilo de visualización n}$${\displaystyle GF(2^{m})}$${\estilo de visualización g}$

Las palabras clave pertenecen al núcleo de la función del síndrome y forman un subespacio de : ${\displaystyle \{0,1\}^{n}}$

${\displaystyle \Gamma (g,L)=\left\{c\in \{0,1\}^{n}\left|\sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\equiv 0\mod g(x)\right.\right\}}$

El código definido por una tupla tiene una dimensión de al menos y una distancia de al menos , por lo que puede codificar mensajes de longitud de al menos utilizando palabras de código de tamaño y corrigiendo al menos errores. Posee una conveniente matriz de verificación de paridad en forma ${\estilo de visualización (g,L)}$${\displaystyle n-mt}$${\estilo de visualización 2t+1}$${\displaystyle n-mt}$${\estilo de visualización n}$${\displaystyle \left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor }$ ${\estilo de visualización H}$

${\displaystyle H=VD={\begin{pmatrix}1&1&1&\cdots &1\\L_{1}^{1}&L_{2}^{1}&L_{3}^{1}&\cdots &L_{n}^{1}\\L_{1}^{2}&L_{2}^{2}&L_{3}^{2}&\cdots &L_{n}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\L_{1}^{t-1}&L_{2}^{t-1}&L_{3}^{t-1}&\cdots &L_{n}^{t-1}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{g(L_{1})}}&&&&\\&{\frac {1}{g(L_{2})}}&&&\\&&{\frac {1}{g(L_{3})}}&&\\&&&\ddots &\\&&&&{\frac {1}{g(L_{n})}}\end{pmatrix}}}$

Tenga en cuenta que esta forma de la matriz de comprobación de paridad, al estar compuesta por una matriz de Vandermonde y una matriz diagonal , comparte la forma con las matrices de comprobación de códigos alternantes , por lo que se pueden utilizar decodificadores alternantes en esta forma. Dichos decodificadores suelen proporcionar solo una capacidad limitada de corrección de errores (en la mayoría de los casos ). ${\estilo de visualización V}$ ${\estilo de visualización D}$${\estilo de visualización t/2}$

Para fines prácticos, la matriz de verificación de paridad de un código Goppa binario se convierte generalmente a una forma binaria más amigable para la computadora mediante una construcción de traza, que convierte la matriz -por- en una matriz binaria -por- escribiendo coeficientes polinómicos de elementos en filas sucesivas. ${\estilo de visualización t}$${\estilo de visualización n}$${\displaystyle GF(2^{m})}$${\estilo de visualización mt}$${\estilo de visualización n}$${\displaystyle GF(2^{m})}$${\estilo de visualización m}$

La decodificación de códigos binarios Goppa se realiza tradicionalmente mediante el algoritmo de Patterson, que proporciona una buena capacidad de corrección de errores (corrige todos los errores de diseño) y también es bastante simple de implementar. ${\estilo de visualización t}$

El algoritmo de Patterson convierte un síndrome en un vector de errores. Se espera que el síndrome de una palabra binaria adopte la forma de ${\displaystyle c=(c_{1},\puntos ,c_{n})}$

${\displaystyle s(x)\equiv \suma _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\mod g(x)}$

Se puede utilizar una forma alternativa de una matriz de verificación de paridad basada en la fórmula para para producir dicho síndrome con una simple multiplicación de matrices.${\estilo de visualización s(x)}$

El algoritmo calcula entonces . Esto falla cuando , pero ese es el caso cuando la palabra de entrada es una palabra de código, por lo que no es necesaria ninguna corrección de errores. ${\displaystyle v(x)\equiv {\sqrt {s(x)^{-1}-x}}\mod g(x)}$${\displaystyle s(x)\equiv 0}$

${\estilo de visualización v(x)}$se reduce a polinomios y utilizando el algoritmo euclidiano extendido , de modo que , mientras que y . ${\displaystyle a(x)}$${\estilo de visualización b(x)}$${\displaystyle a(x)\equiv b(x)\cdot v(x)\mod g(x)}$${\displaystyle \deg(a)\leq \lfloor t/2\rfloor }$${\displaystyle \deg(b)\leq \lfloor (t-1)/2\rfloor }$

Finalmente, el polinomio localizador de errores se calcula como . Nótese que en el caso binario, localizar los errores es suficiente para corregirlos, ya que solo hay otro valor posible. En los casos no binarios, también se debe calcular un polinomio de corrección de errores por separado. ${\displaystyle \sigma(x)=a(x)^{2}+x\cdot b(x)^{2}}$

Si la palabra clave original era decodificable y el vector de error binario era el vector de error, entonces ${\ Displaystyle e = (e_ {1}, \ puntos, e_ {n})}$

${\displaystyle \sigma(x)=\prod_{i=1}^{n}e_{i}(x-L_{i})}$

Por lo tanto, factorizar o evaluar todas las raíces de proporciona suficiente información para recuperar el vector de error y corregir los errores. ${\displaystyle \sigma(x)}$

Los códigos Goppa binarios, considerados como un caso especial de códigos Goppa, tienen la interesante propiedad de que corrigen errores completos, mientras que solo corrigen errores en los casos ternarios y en todos los demás. Asintóticamente, esta capacidad de corrección de errores cumple con el famoso límite de Gilbert-Varshamov . ${\displaystyle \deg(g)}$${\displaystyle \deg(g)/2}$

Debido a la alta capacidad de corrección de errores en comparación con la tasa de código y la forma de la matriz de verificación de paridad (que generalmente es difícilmente distinguible de una matriz binaria aleatoria de rango completo), los códigos binarios Goppa se utilizan en varios criptosistemas postcuánticos , en particular el criptosistema McEliece y el criptosistema Niederreiter .

• Elwyn R. Berlekamp, ​​Códigos Goppa, IEEE Transactions on information theory, vol. IT-19, n.º 5, septiembre de 1973, https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
• Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. "Un resumen de los criptosistemas de tipo McEliece y su seguridad". Journal of Mathematical Cryptology 1, 151–199. MR 2345114. Versión anterior: http://eprint.iacr.org/2006/162/
• Daniel J. Bernstein. "Descodificación de listas para códigos binarios Goppa". http://cr.yp.to/codes/goppalist-20110303.pdf

• Códigos BCH
• Tasa de código
• Corrección de errores de Reed-Solomon