Block Wiedemann algorithm - Revision history

OAbot: Open access bot: arxiv added to citation with #oabot.

2023-08-13T19:37:53Z

Open access bot: arxiv added to citation with #oabot.

← Previous revision		Revision as of 19:37, 13 August 2023
Line 20:		Line 20:
	<div class="center">		<div class="center">
	<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\		<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\
	\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math>.<ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>		\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math>.<ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171\|arxiv=1803.03864 }}</ref>
	</div>		</div>

GünniX: Reflist

2023-03-04T18:04:10Z

Reflist

← Previous revision		Revision as of 18:04, 4 March 2023
Line 5:		Line 5:
	Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>		Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>

	We know that the matrix <math>M</math> has a [[~~Minimal_polynomial_~~(~~linear_algebra~~)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than <math>n</math>. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.		We know that the matrix <math>M</math> has a [[Minimal polynomial (linear algebra)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than <math>n</math>. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.

	But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.		But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.
Line 16:		Line 16:

	== Invariant Factor Calculation ==		== Invariant Factor Calculation ==
	The block Wiedemann algorithm can be used to calculate the leading [[~~Invariant~~ factor~~\|invariant factors~~]] of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is		The block Wiedemann algorithm can be used to calculate the leading [[invariant factor]]s of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is

	<div class="center">		<div class="center">
	<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\		<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\
	\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math> <ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>.		\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math>.<ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>
	</div>		</div>

	== References ==		== References ==
			{{Reflist}}

	Wiedemann, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54-62, 1986.		* Wiedemann, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54-62, 1986.

	D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350.		* D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350.

	Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.		* Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.

	Thomé's paper '[http://hal.archives-ouvertes.fr/docs/00/10/34/17/PDF/jsc.pdf Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm]' uses a more sophisticated [[Fast Fourier transform\|FFT]]-based algorithm for computing the vector generating polynomials, and describes a practical implementation with ''i''<sub>max</sub> = ''j''<sub>max</sub> = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2<sup>607</sup>−1, and hence to compute discrete logarithms in the field ''GF''(2<sup>607</sup>).		* Thomé's paper '[http://hal.archives-ouvertes.fr/docs/00/10/34/17/PDF/jsc.pdf Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm]' uses a more sophisticated [[Fast Fourier transform\|FFT]]-based algorithm for computing the vector generating polynomials, and describes a practical implementation with ''i''<sub>max</sub> = ''j''<sub>max</sub> = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2<sup>607</sup>−1, and hence to compute discrete logarithms in the field ''GF''(2<sup>607</sup>).

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

Bruce1ee: fixed lint errors – obsolete center HTML tags

2023-03-01T17:36:41Z

fixed lint errors – obsolete center HTML tags

← Previous revision		Revision as of 17:36, 1 March 2023
Line 18:		Line 18:
	The block Wiedemann algorithm can be used to calculate the leading [[Invariant factor\|invariant factors]] of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is		The block Wiedemann algorithm can be used to calculate the leading [[Invariant factor\|invariant factors]] of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is

	<center>		<div class="center">
	<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\		<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\
	\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math> <ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>.		\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math> <ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>.
	</~~center~~>		</div>

	== References ==		== References ==

198.52.235.3: Added probability bound for leading invariant factor calculation using the block Wiedemann algorithm.

2023-03-01T17:11:59Z

Added probability bound for leading invariant factor calculation using the block Wiedemann algorithm.

← Previous revision		Revision as of 17:11, 1 March 2023
Line 14:		Line 14:

	It turns out, by a generalization of the Berlekamp–Massey algorithm to provide a sequence of small matrices, that you can take the sequence produced for a large number of vectors and generate a kernel vector of the original large matrix. You need to compute <math> y_i \cdot M^t x_j</math> for some <math>i = 0 \ldots i_\max, j=0 \ldots j_\max, t = 0 \ldots t_\max</math> where <math>i_\max, j_\max, t_\max</math> need to satisfy <math>t_\max > \frac{d}{i_\max} + \frac{d}{j_\max} + O(1)</math> and <math>y_i</math> are a series of vectors of length n; but in practice you can take <math>y_i</math> as a sequence of unit vectors and simply write out the first <math>i_\max</math> entries in your vectors at each time ''t''.		It turns out, by a generalization of the Berlekamp–Massey algorithm to provide a sequence of small matrices, that you can take the sequence produced for a large number of vectors and generate a kernel vector of the original large matrix. You need to compute <math> y_i \cdot M^t x_j</math> for some <math>i = 0 \ldots i_\max, j=0 \ldots j_\max, t = 0 \ldots t_\max</math> where <math>i_\max, j_\max, t_\max</math> need to satisfy <math>t_\max > \frac{d}{i_\max} + \frac{d}{j_\max} + O(1)</math> and <math>y_i</math> are a series of vectors of length n; but in practice you can take <math>y_i</math> as a sequence of unit vectors and simply write out the first <math>i_\max</math> entries in your vectors at each time ''t''.

			== Invariant Factor Calculation ==
			The block Wiedemann algorithm can be used to calculate the leading [[Invariant factor\|invariant factors]] of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is

			<center>
			<math>p \geq \begin{cases} 1/64, & \text{if }b = k+1\text{ and } q=2 \\ \left( 1 - \frac{3}{2^{b-k}} \right)^2 \geq 1/16 & \text{if }b \geq k+2\text{ and } q=2 \\
			\left( 1 - \frac{2}{q^{b-k}} \right)^2 \geq 1/9 & \text{if }b \geq k+1\text{ and }q > 2\end{cases}</math> <ref>{{Cite journal \|last=Harrison \|first=Gavin \|last2=Johnson \|first2=Jeremy \|last3=Saunders \|first3=B. David \|date=2022-01-01 \|title=Probabilistic analysis of block Wiedemann for leading invariant factors \|url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 \|journal=Journal of Symbolic Computation \|language=en \|volume=108 \|pages=98–116 \|doi=10.1016/j.jsc.2021.06.005 \|issn=0747-7171}}</ref>.
			</center>

	== References ==		== References ==

AlexanderJHabib: I did not know that the British spelling for generalization was so different. Change it back if you like. No harm meant.

2022-06-07T09:36:12Z

I did not know that the British spelling for generalization was so different. Change it back if you like. No harm meant.

← Previous revision		Revision as of 09:36, 7 June 2022
Line 1:		Line 1:
	The '''block Wiedemann algorithm''' for computing [[kernel (linear algebra)\|kernel]] [[vector space\|vectors]] of a [[matrix (mathematics)\|matrix]] over a [[finite field]] is a ~~generalisation~~ by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.		The '''block Wiedemann algorithm''' for computing [[kernel (linear algebra)\|kernel]] [[vector space\|vectors]] of a [[matrix (mathematics)\|matrix]] over a [[finite field]] is a generalization by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.

	== Wiedemann's algorithm ==		== Wiedemann's algorithm ==

Ciphergoth: wikilink the lede

2022-04-21T16:17:33Z

wikilink the lede

← Previous revision		Revision as of 16:17, 21 April 2022
Line 1:		Line 1:
	The '''block Wiedemann algorithm''' for computing kernel vectors of a [[matrix (mathematics)\|matrix]] over a finite field is a generalisation by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.		The '''block Wiedemann algorithm''' for computing [[kernel (linear algebra)\|kernel]] [[vector space\|vectors]] of a [[matrix (mathematics)\|matrix]] over a [[finite field]] is a generalisation by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.

	== Wiedemann's algorithm ==		== Wiedemann's algorithm ==

172.88.126.150: Algorithm and modification to it were wrongly named and attributed. Also I included references to the original papers.

2021-05-12T00:06:53Z

Algorithm and modification to it were wrongly named and attributed. Also I included references to the original papers.

← Previous revision		Revision as of 00:06, 12 May 2021
Line 1:		Line 1:
	The '''block Wiedemann algorithm''' for computing kernel vectors of a [[matrix (mathematics)\|matrix]] over a finite field is a generalisation of an algorithm due to ~~[[Don~~ ~~Coppersmith]]~~.		The '''block Wiedemann algorithm''' for computing kernel vectors of a [[matrix (mathematics)\|matrix]] over a finite field is a generalisation by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.

	== ~~Coppersmith~~'s algorithm ==		== Wiedemann's algorithm ==

	Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>		Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>
Line 9:		Line 9:
	But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.		But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.

	== The block Wiedemann algorithm ==		== The block Wiedemann (or Coppersmith-Wiedemann) algorithm ==

	The natural implementation of sparse matrix arithmetic on a computer makes it easy to compute the sequence ''S'' in parallel for a number of vectors equal to the width of a machine word – indeed, it will normally take no longer to compute for that many vectors than for one. If you have several processors, you can compute the sequence S for a different set of random vectors in parallel on all the computers.		The natural implementation of sparse matrix arithmetic on a computer makes it easy to compute the sequence ''S'' in parallel for a number of vectors equal to the width of a machine word – indeed, it will normally take no longer to compute for that many vectors than for one. If you have several processors, you can compute the sequence S for a different set of random vectors in parallel on all the computers.
Line 16:		Line 16:

	== References ==		== References ==

			Wiedemann, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54-62, 1986.

			D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350.

	Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.		Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.

166.137.178.185 at 21:40, 13 May 2016

2016-05-13T21:40:56Z

← Previous revision		Revision as of 21:40, 13 May 2016
Line 3:		Line 3:
	== Coppersmith's algorithm ==		== Coppersmith's algorithm ==

	Let M be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length n, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix M; let y be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>		Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>

	We know that the matrix M has a [[Minimal_polynomial_(linear_algebra)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than n. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.		We know that the matrix <math>M</math> has a [[Minimal_polynomial_(linear_algebra)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than <math>n</math>. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.

	But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \forall r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.		But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.

	== The block Wiedemann algorithm ==		== The block Wiedemann algorithm ==

166.137.178.185 at 21:18, 13 May 2016

2016-05-13T21:18:13Z

← Previous revision		Revision as of 21:18, 13 May 2016
Line 3:		Line 3:
	== Coppersmith's algorithm ==		== Coppersmith's algorithm ==

	Let M be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length n, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix M; let y be any other vector of length n, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>		Let M be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length n, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix M; let y be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>

	We know that the matrix M has a [[Minimal_polynomial_(linear_algebra)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than n. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.		We know that the matrix M has a [[Minimal_polynomial_(linear_algebra)\|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than n. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.

88.137.8.229: /* References */

2014-03-30T19:03:57Z

References

← Previous revision		Revision as of 19:03, 30 March 2014
Line 19:		Line 19:
	Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.		Villard's 1997 research report '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf A study of Coppersmith's block Wiedemann algorithm using matrix polynomials]' (the cover material is in French but the content in English) is a reasonable description.

	Thomé's paper '[http://~~citeseer~~.~~ist~~.~~psu.edu~~/rd/~~13850609%2C564537%2C1%2C0.25%2CDownload~~/~~http:~~//~~citeseer.ist.psu.edu~~/~~cache~~/~~papers/cs/27081/http:zSzzSzwww.lix.polytechnique.frzSzLabozSzEmmanuel.ThomezSzpubliszSzjsc.pdf/subquadratic-computation-of-vector~~.pdf Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm]' uses a more sophisticated [[Fast Fourier transform\|FFT]]-based algorithm for computing the vector generating polynomials, and describes a practical implementation with ''i''<sub>max</sub> = ''j''<sub>max</sub> = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2<sup>607</sup>−1, and hence to compute discrete logarithms in the field ''GF''(2<sup>607</sup>).		Thomé's paper '[http://hal.archives-ouvertes.fr/docs/00/10/34/17/PDF/jsc.pdf Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm]' uses a more sophisticated [[Fast Fourier transform\|FFT]]-based algorithm for computing the vector generating polynomials, and describes a practical implementation with ''i''<sub>max</sub> = ''j''<sub>max</sub> = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2<sup>607</sup>−1, and hence to compute discrete logarithms in the field ''GF''(2<sup>607</sup>).

	{{Numerical linear algebra}}		{{Numerical linear algebra}}