Algoritmo de Wiedemann en bloques

El algoritmo de bloques de Wiedemann para calcular vectores de núcleo de una matriz sobre un campo finito es una generalización de Don Coppersmith de un algoritmo de Doug Wiedemann.

Sea una matriz cuadrada sobre un cuerpo finito F, sea un vector aleatorio de longitud , y sea . Considérese la secuencia de vectores obtenida al multiplicar repetidamente el vector por la matriz ; sea cualquier otro vector de longitud , y considérese la secuencia de elementos del cuerpo finito${\estilo de visualización M}$${\displaystyle n\veces n}$ ${\displaystyle x_{\mathrm {base}}}$${\estilo de visualización n}$${\displaystyle x=Mx_{\mathrm {base}}}$${\displaystyle S=\left[x,Mx,M^{2}x,\ldots \right]}$${\estilo de visualización M}$${\estilo de visualización y}$${\estilo de visualización n}$${\displaystyle S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]}$

Sabemos que la matriz tiene un polinomio mínimo ; por el teorema de Cayley-Hamilton sabemos que este polinomio es de grado (al que llamaremos ) no mayor que . Digamos . Entonces ; por lo que el polinomio mínimo de la matriz aniquila la secuencia y, por lo tanto , . ${\estilo de visualización M}$${\estilo de visualización n_{0}}$${\estilo de visualización n}$${\displaystyle \suma _{r=0}^{n_{0}}p_{r}M^{r}=0}$${\displaystyle \sum_{r=0}^{n_{0}}y\cdot(p_{r}(M^{r}x))=0}$${\estilo de visualización S}$$Estilo de visualización S_{y}}$

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 a , en realidad aniquila a ; por lo que tenemos . Luego aprovechamos la definición inicial de para decir que y por lo tanto es un vector kernel de , con suerte distinto de cero . ${\displaystyle q_{0}\lpuntos q_{L}}$${\displaystyle \sum _{i=0}^{L}q_{i}S_{y}[{i+r}]=0\;\para todo \;r}$${\displaystyle y\cdot S}$${\estilo de visualización S}$${\displaystyle \suma _{i=0}^{L}q_{i}M^{i}x=0}$${\estilo de visualización x}$${\displaystyle M\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }=0}$${\displaystyle \suma _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base}}}$${\estilo de visualización M}$

La implementación natural de la aritmética de matrices dispersas en una computadora facilita el cálculo de la secuencia S en paralelo para una cantidad de vectores igual al ancho de una palabra de máquina; de hecho, normalmente no se necesitará más tiempo para calcular esa cantidad de vectores que para calcular uno solo. 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, se puede tomar la secuencia producida para una gran cantidad de vectores y generar un vector kernel de la matriz grande original. Es necesario calcular para algunos donde se necesita satisfacer y son una serie de vectores de longitud n; pero en la práctica se puede tomar como una secuencia de vectores unitarios y simplemente escribir las primeras entradas en los vectores en cada momento t . ${\displaystyle y_{i}\cdot M^{t}x_{j}}$${\displaystyle i=0\ldots i_{\max},j=0\ldots j_{\max},t=0\ldots t_{\max}}$${\displaystyle i_{\max},j_{\max},t_{\max}}$${\displaystyle t_{\max}>{\frac {d}{i_{\max}}}+{\frac {d}{j_{\max}}}+O(1)}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$${\displaystyle i_{\max}}$

El algoritmo de bloques de Wiedemann se puede utilizar para calcular los factores invariantes principales de la matriz, es decir, los bloques más grandes de la forma normal de Frobenius . Dados y donde es un cuerpo finito de tamaño , la probabilidad de que los factores invariantes principales de se conserven en es ${\displaystyle M\in F_{q}^{n\times n}}$${\displaystyle U,V\en F_{q}^{b\times n}}$$Estilo de visualización Fq$${\estilo de visualización q}$${\estilo de visualización p}$${\displaystyle k<b}$${\estilo de visualización M}$${\displaystyle \suma _{i=0}^{2n-1}UM^{i}V^{T}x^{i}}$

• Wiedemann, D., "Resolución de ecuaciones lineales dispersas sobre campos finitos", IEEE Trans. Inf. Theory IT-32, págs. 54-62, 1986.

• D. Coppersmith, Solución de ecuaciones lineales homogéneas sobre GF(2) mediante el algoritmo de bloques de Wiedemann, Math. Comp. 62 (1994), 333-350.

• El informe de investigación de Villard de 1997 'Un estudio del algoritmo de bloques Wiedemann de Coppersmith utilizando polinomios matriciales' (el material de la portada 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 bloques Wiedemann' 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 vector kernel de una matriz de 484603×484603 de entradas módulo 2 ⁶⁰⁷ −1 y, por lo tanto, para calcular logaritmos discretos en el campo GF (2 ⁶⁰⁷ ).