El algoritmo de bloques de Wiedemann para calcular los vectores del núcleo de una matriz sobre un campo finito es una generalización de Don Coppersmith de un algoritmo de Doug Wiedemann.
Algoritmo de Wiedemann
Dejar frijol matriz cuadrada sobre algún campo finito F, sea ser un vector aleatorio de longitud , y deja . Considere la secuencia de vectores obtenido multiplicando repetidamente el vector por la matriz ; dejar ser cualquier otro vector de longitud , y considere la secuencia de elementos de campo finito
Sabemos que la matriz tiene un polinomio mínimo ; por el teorema de Cayley-Hamilton sabemos que este polinomio es de grado (que llamaremos) no más que . Decir. Luego; por lo que el polinomio mínimo de la matriz aniquila la secuencia y por lo tanto .
Pero el algoritmo de Berlekamp-Massey nos permite calcular de manera relativamente eficiente alguna secuencia con . Nuestra esperanza es que esta secuencia, que por construcción aniquila, en realidad aniquila ; entonces tenemos. A continuación, aprovechamos la definición inicial de decir y entonces es un vector de kernel con suerte distinto de cero de .
El algoritmo de bloque de Wiedemann (o Coppersmith-Wiedemann)
La implementación natural de la aritmética matricial dispersa en una computadora hace que sea fácil calcular la secuencia S en paralelo para un número de vectores igual al ancho de una palabra de máquina; de hecho, normalmente no tomará más tiempo calcular para tantos vectores que para uno. Si tiene varios procesadores, puede calcular la secuencia S para un conjunto diferente de vectores aleatorios en paralelo en todas las computadoras.
Resulta que, mediante una generalización del algoritmo de Berlekamp-Massey para proporcionar una secuencia de matrices pequeñas, puede tomar la secuencia producida para un gran número de vectores y generar un vector kernel de la matriz grande original. Necesitas calcular para algunos dónde Necesito satisfacer y son una serie de vectores de longitud n; pero en la práctica puedes tomar como una secuencia de vectores unitarios y simplemente escriba el primer entradas en sus vectores en cada tiempo t .
Referencias
Wiedemann, D., "Resolver ecuaciones lineales dispersas sobre campos finitos", IEEE Trans. Inf. Teoría IT-32, págs. 54-62, 1986.
D. Calderero, Resolución de ecuaciones lineales homogéneas sobre GF (2) mediante el algoritmo de bloques de Wiedemann, Matemáticas. Comp. 62 (1994), 333-350.
El informe de investigación de Villard de 1997 " Un estudio del algoritmo de bloques de Wiedemann de Coppersmith usando polinomios matriciales " (el material de la cubierta está en francés pero el contenido en inglés) es una descripción razonable.
El artículo de Thomé ' Cálculo subcuadrático de polinomios generadores de vectores y mejora del algoritmo de Wiedemann de bloques ' utiliza un algoritmo basado en FFT más sofisticado para calcular los polinomios generadores de vectores y describe una implementación práctica con i max = j max = 4 utilizada para calcular un kernel vector de una matriz de 484603 × 484603 de entradas módulo 2 607 -1, y por lo tanto calcular logaritmos discretos en el campo GF (2 607 ).