Block Wiedemann-algoritmen

Block Wiedemann-algoritmen för att beräkna kärnvektorer för en matris över ett ändligt fält är en generalisering av Don Coppersmith av en algoritm som beror på Doug Wiedemann.

Wiedemanns algoritm

Låt $M$ vara en $n\times n$ kvadratisk matris över något ändligt fält F, låt $x_{\mathrm {bas} }$ vara en slumpmässig vektor av längden $n$ , och låt $x=Mx_{\mathrm {bas} }$ . Betrakta sekvensen av vektorer $S=\left[x,Mx,M^{2}x,\ldots \right]$ som erhålls genom att upprepade gånger multiplicera vektorn av matrisen $M$ ; låt $y$ vara vilken annan vektor som helst med längden $n$ , och betrakta sekvensen av finita-fältelement ${ \displaystyle S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]}$

Vi vet att matrisen $M$ har ett minimalt polynom ; genom Cayley–Hamilton-satsen vet vi att detta polynom är av grad (som vi kommer att kalla $n_{0}$ ) inte mer än $n$ . Säg $\sum _{r=0}^{n_{0}}p_{r}M^{r}=0$ . Då $\sum _{r=0}^{n_{0}}y\cdot (p_{r}(M^{r}x ))=0$ ; så det minimala polynomet i matrisen utplånar sekvensen $S$ och därmed $S_{y}$ .

Men Berlekamp–Massey-algoritmen tillåter oss att relativt effektivt beräkna någon sekvens $q_{0}\ldots q_{L}$ med ${ \displaystyle \sum _{i=0}^{L}q_{i}S_{y}[{i+r}]=0\;\forall \;r}$ . Vår förhoppning är att denna sekvens, som genom konstruktion förintar $y\cdot S$ , faktiskt förintar $S$ ; så vi har $\sum _{i=0}^{L}q_{i}M^{i}x=0$ . Vi drar då fördel av den initiala definitionen av $x$ för att säga $M\sum _{i=0}^{L}q_{ i}M^{i}x_{\mathrm {bas} }=0$ och så $\sum _{i=0}^{L}q_{ i}M^{i}x_{\mathrm {base} }$ är en förhoppningsvis icke-noll kärnvektor av $M$ .

Block Wiedemann (eller Coppersmith-Wiedemann) algoritm

Den naturliga implementeringen av gles matrisaritmetik på en dator gör det enkelt att beräkna sekvensen S parallellt för ett antal vektorer som är lika med bredden på ett maskinord – i själva verket tar det normalt inte längre tid att beräkna för så många vektorer än för ett. Om du har flera processorer kan du beräkna sekvensen S för en annan uppsättning slumpmässiga vektorer parallellt på alla datorer.

Det visar sig, genom en generalisering av Berlekamp–Massey-algoritmen för att tillhandahålla en sekvens av små matriser, att du kan ta sekvensen som produceras för ett stort antal vektorer och generera en kärnvektor av den ursprungliga stora matrisen. Du måste beräkna $y_{i}\cdot M^{t}x_{j}$ för vissa ${ \displaystyle i=0\ldots i_{\max },j=0\ldots j_{\max },t=0\ldots t_{\max }} där i max , j max$ , $\ max },j_{\max },t_{\max }}$ måste uppfylla $t_{\max }>{\frac {d}{i_ {\max }}}+{\frac {d}{j_{\max }}}+O(1)$ och $y_{i}$ är en serie vektorer med längden n; men i praktiken kan du ta $y_{i}$ som en sekvens av enhetsvektorer och helt enkelt skriva ut de första ${\displaystyle i_{\max }}-$ posterna i dina vektorer vid varje gång t .

Wiedemann, D., "Lösa glesa linjära ekvationer över ändliga fält," IEEE Trans. Inf. Theory IT-32, s. 54-62, 1986.

D. Coppersmith, Lösa homogena linjära ekvationer över GF(2) via block Wiedemann-algoritm, Math. Comp. 62 (1994), 333-350.

Villards forskningsrapport från 1997 ' A study of Coppersmith's block Wiedemann algorithm using matrix polynomials ' (omslagsmaterialet är på franska men innehållet på engelska) är en rimlig beskrivning.

Thomés artikel ' Subquadratic computation of vektorgenererande polynom och förbättring av block Wiedemann-algoritmen ' använder en mer sofistikerad FFT -baserad algoritm för att beräkna vektorgenererande polynom, och beskriver en praktisk implementering med i _max = j _max = 4 som används för att beräkna en kärna vektor av en 484603×484603 matris av poster modulo 2 ⁶⁰⁷ −1, och därmed för att beräkna diskreta logaritmer i fältet GF (2 ⁶⁰⁷ ).