Wiedemann Algorithm

Wiedemann Algorithm - an algorithm that allows you to obtain a solution of a system of linear equations $Ax=b,b\neq 0$ ${\ displaystyle Ax = b, b \ neq 0}$ ${\ displaystyle Ax = b, b \ neq 0}$ over the final field $K=GF(q)$ ${\ displaystyle K = GF (q)}$ ${\ displaystyle K = GF (q)}$ . It was proposed by Douglas Wiedemann ( born Douglas Wiedemann ) in 1986. For some time after the publication of the article, the algorithm did not receive much support and was considered suitable only for obtaining the best estimates of complexity ^[1] . But later Wiedemann's algorithms were implemented on a computer and were used, for example, to search for factoring polynomials over finite fields.

History

Wiedemann's algorithms were presented to the public in the last century. In 1986, a January issue of IEEE Transactions on Information Theory published an article by Douglas Wiedemann entitled Solving sparse linear equations over finite fields . It described algorithms for solving a system of linear equations over a finite field in the case when the matrix of the system is sparse . Moreover, the article examined cases with different sparse matrices. Also, the rationale of the algorithms and the assessment of the complexity of their work were published in the article ^[2] .

Task

The algorithm is needed to solve a system of linear equations $Ax=b,b\neq 0$ ${\ displaystyle Ax = b, b \ neq 0}$ $Ax=b,b\neq 0$ . Matrix $A$ ${\ displaystyle A}$ $A$ has dimension $n\times n$ ${\ displaystyle n \ times n}$ $n\times n$ and is assumed to be sparse , the number of nonzero elements in it is equal to $w$ ${\ displaystyle w}$ $w$ ^[1] .

Theory

Using matrix $A$ ${\ displaystyle A}$ $A$ a non-degenerate linear map (which is also denoted by $A$ ${\ displaystyle A}$ $A$ ) in space $\mathrm {K} ^{n}$ ${\ displaystyle \ mathrm {K} ^ {n}}$ $\mathrm {K} ^{n}$ . Space considered $S$ ${\ displaystyle S}$ $S$ generated by many vectors $\left\{{(A^{i}b_{k})}\right\}_{i=0,1,2}$ ${\ displaystyle \ left \ {{(A ^ {i} b_ {k})} \ right \} _ {i = 0,1,2}}$ $\left\{{(A^{i}b_{k})}\right\}_{i=0,1,2}$ and is determined $A_{S}=A|_{S}$ ${\ displaystyle A_ {S} = A | _ {S}}$ $A_{S}=A|_{S}$ - linear display $S$ ${\ displaystyle S}$ $S$ on $S$ ${\ displaystyle S}$ $S$ .

We denote $f_{z}\in \mathrm {K} ^{n}$ ${\ displaystyle f_ {z} \ in \ mathrm {K} ^ {n}}$ $f_{z}\in \mathrm {K} ^{n}$ - minimal polynomial $A_{S}$ ${\ displaystyle A_ {S}}$ $A_{S}$ , i.e., a nonzero polynomial of the least degree, such that $f(A_{s})$ ${\ displaystyle f (A_ {s})}$ $f(A_{s})$ is a null mapping $S$ ${\ displaystyle S}$ $S$ , moreover, normalized so that its free term is equal to unity. Note that if $g(z)\in \mathrm {K} [z]$ ${\ displaystyle g (z) \ in \ mathrm {K} [z]}$ $g(z)\in \mathrm {K} [z]$ then $g(A_{s})$ ${\ displaystyle g (A_ {s})}$ $g(A_{s})$ - zero mapping if and only if $g(A)b=0$ ${\ displaystyle g (A) b = 0}$ $g(A)b=0$ . Besides, $f(z)$ ${\ displaystyle f (z)}$ $f(z)$ divides polynomial $det(zl_{n}-A)$ ${\ displaystyle det (zl_ {n} -A)}$ $det(zl_{n}-A)$ , and therefore $degf(z)\leqslant n$ ${\ displaystyle degf (z) \ leqslant n}$ $degf(z)\leqslant n$ .

We denote $d=degf(z),f(z)=\sum _{i=0}^{d}{f[i]z^{i}}$ ${\ displaystyle d = degf (z), f (z) = \ sum _ {i = 0} ^ {d} {f [i] z ^ {i}}}$ $d=degf(z),f(z)=\sum _{i=0}^{d}{f[i]z^{i}}$ where $f[i]\in \mathrm {K} ^{n}$ ${\ displaystyle f [i] \ in \ mathrm {K} ^ {n}}$ $f[i]\in \mathrm {K} ^{n}$ - coefficients $f(z)$ ${\ displaystyle f (z)}$ $f(z)$ . If you can find $f(z)$ ${\ displaystyle f (z)}$ then system solution $Ax=b,b\neq 0$ ${\ displaystyle Ax = b, b \ neq 0}$ also located: since $f(A)b=0$ ${\ displaystyle f (A) b = 0}$ and $f[0]=1$ ${\ displaystyle f [0] = 1}$ then

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$

Let be $u$ ${\ displaystyle u}$ is any fixed vector from $\mathrm {K} ^{n}$ ${\ displaystyle \ mathrm {K} ^ {n}}$ . Denote the standard bilinear mapping $\mathrm {K} ^{n}$ ${\ displaystyle \ mathrm {K} ^ {n}}$ at $\mathrm {K}$ ${\ displaystyle \ mathrm {K}}$ as $(,)$ ${\ displaystyle (,)}$ , i.e $((v_{1},...,v_{n}),(w_{1},...,w_{n}))=\sum _{i=1}^{n}{v_{i}w_{i}}$ ${\ displaystyle ((v_ {1}, ..., v_ {n}), (w_ {1}, ..., w_ {n})) = \ sum _ {i = 1} ^ {n} { v_ {i} w_ {i}}}$ .

Because $f(A)b=0$ ${\ displaystyle f (A) b = 0}$ then the sequence

$(u,A^{i}b),i=0,1,2,...,$ ${\ displaystyle (u, A ^ {i} b), i = 0,1,2, ...,}$

satisfies a linear recurrence relation whose characteristic polynomial is $f(z)$ ${\ displaystyle f (z)}$ . Let be $f_{u}(z)$ ${\ displaystyle f_ {u} (z)}$ is the characteristic polynomial of the shortest recurrence relation. Then $f(z)|f_{u}(z)$ ${\ displaystyle f (z) | f_ {u} (z)}$ . Indeed, if divided by the remainder

$f(z)=q(z)f_{u}(z)+r(z)$ {\ displaystyle f (z) = q (z) f_ {u} (z) + r (z)} , $degr(z)<deg~f_{u}(z)$ ${\ displaystyle degr (z) <deg ~ f_ {u} (z)}$

then from the equalities

$0=(u,f(A)b)=(u,q(A)f_{u}(A)b)+(u,r(A)b)$ ${\ displaystyle 0 = (u, f (A) b) = (u, q (A) f_ {u} (A) b) + (u, r (A) b)}$ ,

$(u,f_{u}(A)A^{j}b)=0,j=0,1,2,...,$ ${\ displaystyle (u, f_ {u} (A) A ^ {j} b) = 0, j = 0,1,2, ...,}$

and minimality $f_{u}(z)$ ${\ displaystyle f_ {u} (z)}$ will follow that $r(z)=0$ ${\ displaystyle r (z) = 0}$ . Since a free member $f(z)$ ${\ displaystyle f (z)}$ equal to one, then we can assume that the free term $f_{u}(z)$ ${\ displaystyle f_ {u} (z)}$ equal to one.

Minimal polynomial $f_{u}(z)$ ${\ displaystyle f_ {u} (z)}$ for sequence $(u,A^{i}b),i=0,1,2,...,$ ${\ displaystyle (u, A ^ {i} b), i = 0,1,2, ...,}$ can be obtained using the Berlekamp-Messi algorithm ^[3] by its first $2n$ ${\ displaystyle 2n}$ members. There are two methods for solving the original system.

First method. Random Vector Selected $u(z)$ ${\ displaystyle u (z)}$ . Under construction $f_{u}(z)$ ${\ displaystyle f_ {u} (z)}$ and under the assumption that $f(z)=f_{u}(z)$ ${\ displaystyle f (z) = f_ {u} (z)}$ , located $x$ ${\ displaystyle x}$ according to the formula

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$

In this way, with a fairly high probability, a solution can be found ^[2] .

Second method. Let be $b_{0}=b,f_{1}(z)=f_{u_{1}}(z)$ ${\ displaystyle b_ {0} = b, f_ {1} (z) = f_ {u_ {1}} (z)}$ for some vector $u_{1}$ ${\ displaystyle u_ {1}}$ . If the vector $b_{1}=f_{1}(A)b_{0}$ ${\ displaystyle b_ {1} = f_ {1} (A) b_ {0}}$ equals 0 then it is $x$ ${\ displaystyle x}$ according to the formula

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$ (since then $f_{1}(z)=f(z)$ ${\ displaystyle f_ {1} (z) = f (z)}$ )

If $b_{1}\neq 0$ ${\ displaystyle b_ {1} \ neq 0}$ , then the procedure is repeated, that is, a random vector is selected $u_{2}$ ${\ displaystyle u_ {2}}$ and the minimal polynomial is constructed $f_{2}(z)=f_{u_{2}}(z)$ ${\ displaystyle f_ {2} (z) = f_ {u_ {2}} (z)}$ for sequence $(u_{2},A_{i}b_{1})$ ${\ displaystyle (u_ {2}, A_ {i} b_ {1})}$ . If a $b_{2}=f_{2}(A)b_{1}=0$ ${\ displaystyle b_ {2} = f_ {2} (A) b_ {1} = 0}$ then $f(z)=f_{1}(z)f_{2}(z)$ ${\ displaystyle f (z) = f_ {1} (z) f_ {2} (z)}$ and you can find a solution x by the formula

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$ ,

otherwise selected $u_{3}$ ${\ displaystyle u_ {3}}$ and so on.

We prove that if done $k$ ${\ displaystyle k}$ iterations then $f_{1}(z)...f_{k}(z)$ ${\ displaystyle f_ {1} (z) ... f_ {k} (z)}$ divides $f(z)$ ${\ displaystyle f (z)}$ . It was shown above that $f-1(z)|f(z)$ ${\ displaystyle f-1 (z) | f (z)}$ . Further, assuming that $f_{1}(z)...f_{k-1}(z)$ ${\ displaystyle f_ {1} (z) ... f_ {k-1} (z)}$ divides $f(z)$ ${\ displaystyle f (z)}$ , since $f_{k}(z)$ ${\ displaystyle f_ {k} (z)}$ - minimum polynomial for sequence $\left\{(u_{k},A^{i}b_{k-1})\right\}_{i}=\left\{(u_{k},f_{k-1}(A)...f_{1}(A^{j})b)\right\}_{j}$ ${\ displaystyle \ left \ {(u_ {k}, A ^ {i} b_ {k-1}) \ right \} _ {i} = \ left \ {(u_ {k}, f_ {k-1} (A) ... f_ {1} (A ^ {j}) b) \ right \} _ {j}}$ , and the polynomial ${\frac {f(z)}{f_{1}(z)...f_{k-1}(z)}}$ ${\ displaystyle {\ frac {f (z)} {f_ {1} (z) ... f_ {k-1} (z)}}}$ cancels it then ${f_{k}(z)}|{\frac {f(z)}{f_{1}(z)...f_{k-1}(z)}}$ ${\ displaystyle {f_ {k} (z)} | {\ frac {f (z)} {f_ {1} (z) ... f_ {k-1} (z)}}}$ , as required.

Now it’s obvious that if $b_{x}=f_{k}(A)...f_{1}(A)b=0$ ${\ displaystyle b_ {x} = f_ {k} (A) ... f_ {1} (A) b = 0}$ then $f(x)=f_{1}(x)...f_{k}(x)$ ${\ displaystyle f (x) = f_ {1} (x) ... f_ {k} (x)}$ . That is, as soon as the zero vector is found $b_{k}=f_{k}(A)b_{k-1}$ ${\ displaystyle b_ {k} = f_ {k} (A) b_ {k-1}}$ , then you can find a solution to the original system by the formula

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$ ^[4] .

Algorithm 1

In the original article, the algorithm has such a name. Based on it, a deterministic algorithm is constructed, which is called algorithm 2 in the original article ^[5] .

Algorithm Description

Stage 1. Equated $b_{0}=b,k=0,y_{0}=0,d_{0}=0$ ${\ displaystyle b_ {0} = b, k = 0, y_ {0} = 0, d_ {0} = 0}$ .

2 stage. If a $b_{k}=0$ ${\ displaystyle b_ {k} = 0}$ then the solution is $x=-y_{k}$ ${\ displaystyle x = -y_ {k}}$ , and the algorithm stops working.

3 stage. Random Vector Selected $u_{k+1}\in \mathrm {K} ^{n},u_{k+1}\neq 0$ ${\ displaystyle u_ {k + 1} \ in \ mathrm {K} ^ {n}, u_ {k + 1} \ neq 0}$ .

4th stage. Calculate first $2(n-d_{k})$ ${\ displaystyle 2 (n-d_ {k})}$ sequence members $\left\{{(u_{k+1},A^{i}b_{k})}\right\}_{i=0}^{\infty }$ ${\ displaystyle \ left \ {{(u_ {k + 1}, A ^ {i} b_ {k})} \ right \} _ {i = 0} ^ {\ infty}}$ .

5 stage. Calculate the minimum polynomial $f_{k+1}(z)$ ${\ displaystyle f_ {k + 1} (z)}$ sequences from the 4th stage, and to normalize it so that its free term is equal to one. This can be done using the Berlekamp-Messi algorithm .

6 stage. Assign

$y_{k+1}=y_{k}+{\hat {f}}_{k+1}(A)b_{k}$ ${\ displaystyle y_ {k + 1} = y_ {k} + {\ hat {f}} _ {k + 1} (A) b_ {k}}$ where ${\hat {f}}(z)={\frac {f(z)-f(0)}{z}}$ ${\ displaystyle {\ hat {f}} (z) = {\ frac {f (z) -f (0)} {z}}}$

$b_{k+1}=b_{0}+Ay_{k+1}$ ${\ displaystyle b_ {k + 1} = b_ {0} + Ay_ {k + 1}}$ ,

$d_{k+1}=d_{k}+deg~f_{k+1}(z)$ ${\ displaystyle d_ {k + 1} = d_ {k} + deg ~ f_ {k + 1} (z)}$ .

7th stage. Assign $k=k+1$ ${\ displaystyle k = k + 1}$ and return to the second stage ^[5] .

Justification of the correctness of the algorithm using the method of mathematical induction

${\hat {f}}(z)={\frac {f(z)-f(0)}{z}}$ ${\ displaystyle {\ hat {f}} (z) = {\ frac {f (z) -f (0)} {z}}}$ matches the right side of the formula $x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$ unsigned minus sign. At $k=0$ ${\ displaystyle k = 0}$ is selected $u_{1}$ ${\ displaystyle u_ {1}}$ being considered $2n$ ${\ displaystyle 2n}$ sequence members $\left\{{(u_{1},A^{i}b_{0})}\right\}_{i=0,1,2}$ ${\ displaystyle \ left \ {{(u_ {1}, A ^ {i} b_ {0})} \ right \} _ {i = 0,1,2}}$ and is located $f_{1}(x)$ ${\ displaystyle f_ {1} (x)}$ according to the Berlekamp-Messi algorithm . Then $y_{1}={\hat {f}}_{1}(A)b,b_{1}=b_{0}+Ay_{1}=b+A{\frac {f_{1}(A)-1}{A}}b=f_{1}(A)b,d_{1}=degf_{1}(z)$ ${\ displaystyle y_ {1} = {\ hat {f}} _ {1} (A) b, b_ {1} = b_ {0} + Ay_ {1} = b + A {\ frac {f_ {1} (A) -1} {A}} b = f_ {1} (A) b, d_ {1} = degf_ {1} (z)}$ .

Let after $k$ ${\ displaystyle k}$ pass algorithm performed equality

$y_{k}={\frac {f_{k}(A)...f_{1}(A)-1}{A}}b$ ${\ displaystyle y_ {k} = {\ frac {f_ {k} (A) ... f_ {1} (A) -1} {A}} b}$

$b_{k}=f_{k}(A)...f_{1}(A)b$ ${\ displaystyle b_ {k} = f_ {k} (A) ... f_ {1} (A) b}$

Then after $k+1$ ${\ displaystyle k + 1}$ passage

$y_{k+1}=y_{k}+{\hat {f}}_{k+1}(A)b_{k}={\frac {f_{k}(A)...f_{1}(A)-1}{A}}b+{\frac {f_{k+1}(A)-1}{A}}f_{k}(A)...f_{1}(A)b={\frac {f_{k+1}(A)...f_{1}(A)-1}{A}}b$ ${\ displaystyle y_ {k + 1} = y_ {k} + {\ hat {f}} _ {k + 1} (A) b_ {k} = {\ frac {f_ {k} (A) ... f_ {1} (A) -1} {A}} b + {\ frac {f_ {k + 1} (A) -1} {A}} f_ {k} (A) ... f_ {1} ( A) b = {\ frac {f_ {k + 1} (A) ... f_ {1} (A) -1} {A}} b}$ ,

$b_{k+1}=b_{k}+A{\frac {f_{k+1}(A)...f_{1}(A)-1}{A}}b=f_{k+1}(A)...f_{1}(A)b$ ${\ displaystyle b_ {k + 1} = b_ {k} + A {\ frac {f_ {k + 1} (A) ... f_ {1} (A) -1} {A}} b = f_ { k + 1} (A) ... f_ {1} (A) b}$

That is, the formulas for $y_{k}$ ${\ displaystyle y_ {k}}$ and $b_{k}$ ${\ displaystyle b_ {k}}$ saved. Now the correctness of the algorithm follows from the theory section ^[6] .

Deterministic Algorithm

Algorithm Description

Stage 1. Find value $A^{i}b,i=0,1,...,2n-1$ ${\ displaystyle A ^ {i} b, i = 0,1, ..., 2n-1}$ .

2 stage. Equate to zero $k$ ${\ displaystyle k}$ , but $g_{0}(z)$ ${\ displaystyle g_ {0} (z)}$ unit.

3 stage. Assign $u_{k+1}=(0,...,0,1,0,...,0)$ ${\ displaystyle u_ {k + 1} = (0, ..., 0,1,0, ..., 0)}$ (unit is on $k+1$ ${\ displaystyle k + 1}$ location).

4th stage. Find sequence $(u_{k+1},A^{i}b),i=0,1,...,2n-1$ ${\ displaystyle (u_ {k + 1}, A ^ {i} b), i = 0,1, ..., 2n-1}$ using the first step.

5 stage. Find sequence $(u_{k+1},g_{k}(A)A^{i}b),i=0,1,...,2n-1-deg~g_{k}(z)$ ${\ displaystyle (u_ {k + 1}, g_ {k} (A) A ^ {i} b), i = 0,1, ..., 2n-1-deg ~ g_ {k} (z)}$ , you can use the discrete Fourier transform ^[5] .

6 stage. Find the minimal polynomial $f_{k+1}(z)$ ${\ displaystyle f_ {k + 1} (z)}$ with a free term equal to unity using the Berlekamp-Messi algorithm .

7th stage. Assign $g_{k+1}(z)=f_{k+1}(z)g_{k}(z)$ ${\ displaystyle g_ {k + 1} (z) = f_ {k + 1} (z) g_ {k} (z)}$ .

8 stage. Click to enlarge $k$ ${\ displaystyle k}$ per unit. If a $deg~g_{k}(z)<n$ ${\ displaystyle deg ~ g_ {k} (z) <n}$ and $k<n$ ${\ displaystyle k <n}$ then return to stage 3.

9th stage. For polynomial $f(z)=g_{k}(z)$ ${\ displaystyle f (z) = g_ {k} (z)}$ using the values found in the first stage $A^{i}b$ ${\ displaystyle A ^ {i} b}$ find a solution $x$ ${\ displaystyle x}$ systems using the formula

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ ${\ displaystyle x = - \ sum _ {i = 1} ^ {d} {f [i] A ^ {i-1} b}}$ ^[5] .

Justification of algorithm correctness

Note that in fact the algorithm works the same as Algorithm 1, only vectors $u_{k}$ ${\ displaystyle u_ {k}}$ are not chosen randomly, but there is an enumeration of unit vectors $(0,...,0,1,0,...,0)$ ${\ displaystyle (0, ..., 0,1,0, ..., 0)}$ . It's obvious that $g_{k}(z)=f_{k}(z)...f_{1}(z)$ ${\ displaystyle g_ {k} (z) = f_ {k} (z) ... f_ {1} (z)}$ where $f_{k}(z)$ ${\ displaystyle f_ {k} (z)}$ - minimum polynomial for sequence

$(u_{k},f_{k-1}(A)...f_{1}(A)A^{i}b),i=0,1,...,2n-1-deg(f_{k-1}...f_{1})$ ${\ displaystyle (u_ {k}, f_ {k-1} (A) ... f_ {1} (A) A ^ {i} b), i = 0,1, ..., 2n-1- deg (f_ {k-1} ... f_ {1})}$ .

The algorithm terminated with a certain parameter value $k$ ${\ displaystyle k}$ . Let's pretend that $k<n,deg~g_{k}(z)=n$ ${\ displaystyle k <n, deg ~ g_ {k} (z) = n}$ . Because $deg~f(z)\leqslant n$ ${\ displaystyle deg ~ f (z) \ leqslant n}$ and $g_{k}(z)|f(z)$ ${\ displaystyle g_ {k} (z) | f (z)}$ then $g_{k}(z)=f(z)$ ${\ displaystyle g_ {k} (z) = f (z)}$ . It follows that at step 9, the solution to the original system will be exactly found.

Now consider the case $k=n$ ${\ displaystyle k = n}$ . Since all unit vectors have been enumerated $u_{1},...,u_{n}$ ${\ displaystyle u_ {1}, ..., u_ {n}}$ then vector $g_{n}(A)b$ ${\ displaystyle g_ {n} (A) b}$ orthogonal $u_{1},...,u_{n}$ ${\ displaystyle u_ {1}, ..., u_ {n}}$ . Consequently, $g_{n}(A)b=0$ ${\ displaystyle g_ {n} (A) b = 0}$ . Because $g_{n}(z)|f(z)$ ${\ displaystyle g_ {n} (z) | f (z)}$ and $f(z)$ ${\ displaystyle f (z)}$ is the minimal polynomial then $g_{k}(z)=f(z)$ ${\ displaystyle g_ {k} (z) = f (z)}$ . Therefore, in this case, the correctness of the algorithm ^{[7] was} confirmed.

Algorithm Estimation

For the deterministic algorithm, Wiedemann obtained the following complexity estimate : $O(n(w+n~log(n)log(log(n))))$ ${\ displaystyle O (n (w + n ~ log (n) log (log (n))))}$ ^[5] . The resulting difficulty score is the best known. Thanks to the Wiedemann algorithm, it is possible to improve the complexity estimate in other algorithms using methods for solving linear systems ^[1] .

Similar Algorithms

Where can a solution of a system of linear equations over a finite field come in handy? The need for their solution arises when using factorization algorithms and when solving discrete logarithm problems using factor bases ^[8] . There are a large number of algorithms for obtaining a solution of a system of linear equations over finite fields ^[9] . In addition to Wiedemann's algorithms, one can use Gaussian and structural Gaussian exceptions, the Lanczos algorithm , and the conjugate gradient method ^[10] . Algorithms based on fast matrix multiplication are also known, for example, the Strassen and Koppersmit-Vinograd algorithms ^[11] . Their own algorithms were proposed by Konovaltsev ^[12] and Brillhart ^[13] ^[14] .

In the general case (the matrix of the system is not sparse), the Lanczos algorithm has been used more often lately (probably, together with a structured Gaussian exception to obtain a denser matrix of the subsystem) ^[14] . But in the case of a sparse matrix, it is most efficient to use Wiedemann algorithms, since estimates of their complexity are the best known. Wiedemann's algorithms were not immediately recognized, but later they were nevertheless implemented on a computer. Algorithms were used, for example, to factor polynomials over finite fields ^[1] .

Later various modifications of the original algorithm appeared, for example, the Wiedemann block algorithm ^[1] .

Notes

↑ ¹ ² ³ ⁴ ⁵ Vasilenko O.N., 2003 , p. 287.
↑ ¹ ² Wiedemann DH, 1986 , p. 54-62.
↑ Massey JL, 1969 , p. 122-127.
↑ Vasilenko O.N., 2003 , p. 287-288.
↑ ¹ ² ³ ⁴ ⁵ Wiedemann DH, 1986 , p. 55.
↑ Vasilenko O.N., 2003 , p. 289-290.
↑ Vasilenko O.N., 2003 , p. 290-291.
↑ Vasilenko O.N., 2003 , p. 274-275.
↑ LaMacchia B., Odlyzko A., 1990 , p. 109-133.
↑ Coppersmith D., Odlyzko A., Schroeppel R., 1986 , p. 1-15.
↑ Alekseev V. B., 1988 , p. 189-236.
↑ Konovaltsev I.V., 1967 , p. 269-274.
↑ Brillhart J., 1989 , p. 211-213.
↑ ¹ ² Vasilenko O.N., 2003 , p. 291.

Literature

Vasilenko O. N. Number-theoretic algorithms in cryptography . - M .: ICMMO, 2003 .-- 328 p. - ISBN 5-94057-103-4 .
Wiedemann DH Solving sparce linear equations over finite fields. - 1986. - January ( t. 32 , No. 1 ). - S. 54-62 .
Kaltofen E., Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm (Eng.) // Proceedings of ISSAC'94. - 1994. - S. 90-98 .
Massey JL Shift-register synthesis and BCH decoding (English) // IEEE Trans. Inform. Theory. - 1969. - T. 15 . - S. 122-127 .
Alekseev V. B. Complexity of matrix multiplication. Review (Russian) // Cybernetich. team .. - 1988. - T. 25 . - S. 189-236 .

Konovaltsev I.V. On an algorithm for solving systems of linear equations in finite fields (Russian) // Problems of Cybernetics. - 1967 .-- T. 16 . - S. 269-274 .
Brillhart J. A note on finding depencensies over GF (2) (Eng.) // Utilitas Math. - 1989 .-- T. 36 . - S. 211-213 .
LaMacchia B., Odlyzko A. Solving large sparse linear systems over finite fields (English) // Advances in Cryptology — CRYPTO'90. - 1990 .-- T. 537 . - S. 109-113 .
Coppersmith D., Odlyzko A., Schroeppel R. Discrete logarithms in GF (p) (English) // Algorithmica. - 1986.- T. 1 . - S. 1-15 .

[_3f9f1090edc49ce3-1] ¹ ² ³ ⁴ ⁵ Vasilenko O.N., 2003 , p. 287.

[_4d6ca06d8ca9728d-2] ¹ ² Wiedemann DH, 1986 , p. 54-62.

[_5b57688559c1d1ca-3] Massey JL, 1969 , p. 122-127.

[_70448f331686344e-4] Vasilenko O.N., 2003 , p. 287-288.

[_718abb2ca4bb4a65-5] ¹ ² ³ ⁴ ⁵ Wiedemann DH, 1986 , p. 55.

[_f5ba38869c304647-6] Vasilenko O.N., 2003 , p. 289-290.

[_62d5b870d91813c4-7] Vasilenko O.N., 2003 , p. 290-291.

[_629776e94bb3bffc-8] Vasilenko O.N., 2003 , p. 274-275.

[_13baa9f33325da0e-9] LaMacchia B., Odlyzko A., 1990 , p. 109-133.

[_37f8a1aa8ac4feef-10] Coppersmith D., Odlyzko A., Schroeppel R., 1986 , p. 1-15.

[_42b1c7911f68b0ee-11] Alekseev V. B., 1988 , p. 189-236.

[_d97970f7c095133e-12] Konovaltsev I.V., 1967 , p. 269-274.

[_a78b713e07a7f337-13] Brillhart J., 1989 , p. 211-213.

[_3f9f1190edc49eb6-14] ¹ ² Vasilenko O.N., 2003 , p. 291.

Wiedemann Algorithm

History

Task

Theory

Algorithm 1

Algorithm Description

Justification of the correctness of the algorithm using the method of mathematical induction

Deterministic Algorithm

Algorithm Description

Justification of algorithm correctness

Algorithm Estimation

Similar Algorithms

Notes

Literature

More articles: