Factorización eficiente de polinomios sobre $\Bbb F_2$

Question

Estoy intentando escribir un software que pretende responder genéricamente a la pregunta de qué polinomio generador de Código de Redundancia Cíclica (CRC) se utiliza para un conjunto dado de mensajes de muestra que utilizan el mismo CRC desconocido.

Por ejemplo, aquí hay dos mensajes en hexadecimal que utilizan el mismo CRC:

ee 00 00 00 00 01 20 13 10  (message 1)
ee 00 00 00 00 03 20 a3 23  (message 2)

Dado que los cálculos de CRC son esencialmente división de polinomios sobre GF(2) Podemos considerar que cada cálculo de CRC es $M(x) x^n = Q(x) G(x) + R(x)$ donde $M(x)$ es el mensaje original al que se le añade $n$ ceros, $G(x)$ es el polinomio generador y $R(x)$ es el resto, que es idéntico al valor CRC que se adjunta al final del mensaje. En este caso concreto, el mensaje original es

ee 00 00 00 00 01 20

y el anexo $R(x)$ es 13 10

Dado que estos dos mensajes utilizan el mismo polinomio generador, sabemos que $M_1(x) x^n = Q_1(x) G(x) + R_1(x)$ y $M_2(x) x^n = Q_2(x) G(x) + R_2(x)$ . Restando una de la otra obtenemos: $$\begin{eqnarray*} M_1(x) x^n - M_2(x) x^n &=& Q_1(x) G(x) + R_1(x) - Q_2(x) G(x) - R_2(x)\\ (M_1(x) - M_2(x))x^n - R_1(x) + R_2(x) &=& (Q_1(x)-Q_2(x))G(x)\\ \end{eqnarray*}$$ Dado que la suma y la resta de polinomios sobre GF(2) son idénticas a la operación de suma exclusiva, este resultado significa que la suma exclusiva de los dos mensajes (incluidos los CRC) es idéntica a $(Q_1(x)-Q_2(x))G(x)$ por lo que encontrar el polinomio generador $G(x)$ se puede hacer mediante la factorización de este resultado. En el caso concreto de los dos mensajes anteriores, obtenemos

02 00 b0 33

Debido a la forma en que se calculan los CRC con mayor frecuencia, los bits se "intercambian" para que esto corresponda realmente al polinomio: $x^{30}+x^{11}+x^{10}+x^8+x^7+x^6+x^3+x^2$ . Esto es un factor trivial en $x^2(x^{28}+x^9+x^8+x^6+x^5+x^4+x+1)$ pero ahí es donde me quedo atascado. Sé que en este caso particular, $G(x) = x^{16}+x^{12}+x^5+1$ (que algunos pueden reconocer como el polinomio estándar del CCITT de 16 bits).

¿Cómo puedo escribir un código eficiente para factorizar ese polinomio sobre GF(2) sin recurrir a la fuerza bruta?

Buscando bibliografía que ayudara a responder a esa pregunta, encontré varios trabajos que parecían prometedores:

• http://www-math.upb.de/~aggathen/Publicaciones/gatger96a.ps.gz
• http://www.sciencedirect.com/science/article/pii/S0747717185710553

Sin embargo, soy ingeniero y no matemático, y me parece que no puedo entender lo que significan realmente los documentos y, por tanto, no puedo utilizar los algoritmos inteligentes que pretenden contener. Si no vuelvo a obtener un título en teoría de campos, ¿hay algún medio para aprender a utilizar las técnicas modernas de factorización de polinomios para aplicarlas a este problema?

Answer 1

He tenido ocasión de mencionar el software de matemáticas simbólicas Sage en algunas respuestas, por ejemplo sobre irreducibilidad sobre el campo binario y factorización de polinomios racionales . Una buena manera de hacer experimentos improvisados es con una cuenta de Sage en línea, que ha evolucionado en SageMathCloud .

Para el ejemplo dado en la Pregunta, hice este archivo de trabajo de Sage en línea (crea una cuenta y un nuevo proyecto, y mostrará un archivo de trabajo vacío editable):

P.<x> = GF(2)[ ]
f = x^30 + x^11 + x^10 + x^8 + x^7 + x^6 + x^3 + x^2
f.factor()

La ejecución del proyecto (icono de la izquierda) produce este resultado:

(x + 1) * x^2 * (x^3 + x + 1) * (x^4 + x^3 + x^2 + x + 1) * (x^5 + x^4 + x^3 + x + 1) * (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1)

o en forma más concisa (MathJax):

$$ (x + 1) * x^2 * (x^3 + x + 1) * (x^4 + x^3 + x^2 + x + 1) * (x^5 + x^4 + x^3 + x + 1) * (x^{15} + x^{14} + x^{13} + x^{12} + x^4 + x^3 + x^2 + x + 1) $$

Tenga en cuenta que el "polinomio estándar CCITT de 16 bits" $G(x) = x^{16}+x^{12}+x^5+1$ citado en la Pregunta es en realidad el producto del primero y el último de estos factores irreductibles.

También soy fan de Victor Shoup NTL: una biblioteca para hacer teoría de números una biblioteca C++ portátil y de alto rendimiento que proporciona estructuras de datos y algoritmos para manipular números enteros de longitud arbitraria con signo, y para vectores, matrices y polinomios sobre los números enteros y sobre campos finitos".

A mitad de camino esta página se nos dice que Sage utilizará la biblioteca NTL para los polinomios sobre el campo binario, por ejemplo, para la multiplicación y los GCD, al menos si el comando se enmarca adecuadamente:

sage: x = PolynomialRing(GF(2), 'x').gen()
sage: f = (x^3 - x + 1)*(x + x^2); f
x^5 + x^4 + x^3 + x
sage: g = (x^3 - x + 1)*(x + 1)
sage: f.gcd(g)
x^4 + x^3 + x^2 + 1

La información a nivel de desarrollador es en esta página de documentación de Sage .

En última instancia, es posible que desee construir una tubería para la factorización sobre el campo binario que va directamente contra NTL, cortando el intermediario Sage, como la implementación de C ++ desnudo debe eliminar algunos gastos generales. Información sobre la construcción de la NTL con el La biblioteca GF2X está aquí .

He construido Sage desde el código fuente un par de veces (es un proceso totalmente automatizado pero que requiere mucho tiempo). Si llego a hacer una construcción similar desde el código fuente reciente de la LNT, informaré de mis experiencias aquí.

Finalmente este Documento de 2002 de von zur Gathen y Gerhard , "Factorización de polinomios sobre $\mathbb{F}_2$ ", puede parecerle un relato accesible de las investigaciones que amplían Cantor-Zassenhaus.

Answer 2

... y ahora algo completamente diferente a los enfoques sugeridos en los comentarios.

Para el ejemplo de juguete en el que los datos difieren en un solo bit, el enfoque de factorización puede ser adecuado porque el grado del polinomio de diferencia es pequeño. En general, la diferencia podría ser de un grado mucho mayor y la factorización podría ser una forma ineficiente de resolver el problema.

Sugerencia: dados dos polinomios $M(x)$ y $N(x)$ que se sabe que son múltiplos del polinomio CRC $P(x)$ calcula el máximo común divisor de $M(x)$ y $N(x)$ . La "división larga" es fácil en $\mathbb F_2[x]$ y el gcd resultante es bastante probable que sea $P(x)$ . Si no consigues $P(x)$ (por ejemplo, si sabe $\deg P(x)$ y resulta que $\deg \gcd(M(x), N(x)) > \deg P(x)$ ) de inmediato, al menos tienes (espero) un polinomio de mucho menor grado para tratar de factorizar.