Block_Wiedemann_algorithm
有限体上の行列のカーネルベクトルを計算するためのブロックWiedemannアルゴリズムは、DougWiedemannによるアルゴリズムのDonCoppersmithによる一般化です。
ヴィーデマンのアルゴリズム
させて {M}
豆 ×× {n times n}
ある有限体F上の正方行列、e
{x _ { mathrm {base}}}
長さのランダムなベクトルである {n}
、そして =NS e
{x = Mx _ { mathrm {base}}}
。ベクトルのシーケンスを検討してください =
[ 、 、2 、… ]
{S = left [x、Mx、M ^ {2} x、 ldots right]}
ベクトルに行列を繰り返し乗算することによって得られます {M}
; させて y {y}
他の長さのベクトルである {n}
、および有限体要素のシーケンスを検討します y = [ y
⋅ 、 y ⋅ 、 y ⋅2 … ] {S_ {y} = left [y cdot x、y cdot Mx、y cdot M ^ {2} x ldots right]}
私たちは、マトリックスが {M}
最小多項式を持っています; ケイリー・ハミルトンの定理により、この多項式は次数であることがわかります（これを次数と呼びます）。 0
{n_ {0}}
） に過ぎません {n}
。言う
∑ =
00 NS= 0 { sum _ {r = 0} ^ {n_ {0}} p_ {r} M ^ {r} = 0}
。それで
∑ =00 y ⋅（（ NS（（）。
）。= 0
{ sum _ {r = 0} ^ {n_ {0}} y cdot（p_ {r}（M ^ {r} x））= 0}
; したがって、行列の最小多項式はシーケンスを消滅させます {S}
それゆえ y
{S_ {y}}
。
しかし、Berlekamp–Masseyアルゴリズムを使用すると、いくつかのシーケンスを比較的効率的に計算できます。 0 … L {q_ {0} ldots q_ {L}}
と
∑I = 0
L I y
[ 私+ ]= 0
∀ { sum _ {i = 0} ^ {L} q_ {i} S_ {y} = 0 ; forall ; r}
。私たちの希望は、構造によって消滅するこのシーケンスが消滅することです y ⋅ {y cdot S}
、実際に全滅させる {S}
; だから私たちは持っています∑ I = 0
L I I = 0 { sum _ {i = 0} ^ {L} q_ {i} M ^ {i} x = 0}
。次に、の初期定義を利用します。 {x}
言う ∑I = 0
L I 私e= 0
{M sum _ {i = 0} ^ {L} q_ {i} M ^ {i} x _ { mathrm {base}} = 0}
など
∑I = 0
L I 私e
{ sum _ {i = 0} ^ {L} q_ {i} M ^ {i} x _ { mathrm {base}}}
うまくいけば、のゼロ以外のカーネルベクトルです {M}
。
ブロックWiedemann（またはCoppersmith-Wiedemann）アルゴリズム
コンピューターでのスパース行列演算の自然な実装により、マシンワードの幅に等しい数のベクトルについてシーケンスSを並列に計算することが容易になります。実際、通常、その数のベクトルについて計算するのに、一。複数のプロセッサがある場合は、すべてのコンピュータで並列に異なるランダムベクトルのセットのシーケンスSを計算できます。
Berlekamp–Masseyアルゴリズムを一般化して小さな行列のシーケンスを提供することにより、多数のベクトルに対して生成されたシーケンスを取得して、元の大きな行列のカーネルベクトルを生成できることがわかります。あなたは計算する必要がありますy I
⋅{y_ {i} cdot M ^ {t} x_ {j}}
いくつかのためのI = 0 … I
最大
、 = 0 … 最大
、 = 0 … 最大
{i = 0 ldots i _ { max}、j = 0 ldots j _ { max}、t = 0 ldots t _ { max}}
どこ I 最大、 最大 、 最大
{i _ { max}、j _ { max}、t _ { max}}
満たす必要があります 最大I 大+最大+ O（（ 1 ）。 {t _ { max}> { frac {d} {i _ { max}}} + { frac {d} {j _ { max}}} + O（1）}
{frac {d}{i_{max }}}+{frac {d}{j_{max }}}+O(1)””>
と
y I {y_ {i}}
長さnの一連のベクトルです。しかし実際にはあなたは取ることができますy I
{y_ {i}}
単位ベクトルのシーケンスとして、最初のベクトルを書き出すだけです。 I 最大
{i _ { max}}
各時間tでのベクトルのエントリ。
参考文献
Wiedemann、D。、「有限体上のスパース線形方程式の解法」、IEEETrans。Inf。理論IT-32、pp。54-62、1986。
D.コッパースミス、ブロックWiedemannアルゴリズム、Mathを介してGF（2）上で均一な線形方程式を解きます。コンプ。62（1994）、333-350。
Villardの1997年の調査レポート「行列多項式を使用したCoppersmithのブロックWiedemannアルゴリズムの研究」（表紙はフランス語ですが、内容は英語です）は妥当な説明です。
Thoméの論文「ベクトル生成多項式の準二次計算とブロックWiedemannアルゴリズムの改善」は、ベクトル生成多項式を計算するためのより洗練されたFFTベースのアルゴリズムを 使用し、カーネルの計算に使用されるi max = j max = 4の実際の実装について説明します。 2 607 -1を法とするエントリの484603×484603行列のベクトル。したがって、フィールドGF（2 607）の離散対数を計算します。”