ブロックヴィーデマンアルゴリズム

有限体上の行列の核ベクトルを計算するブロックヴィーデマン アルゴリズムは、Doug Wiedemann によるアルゴリズムをDon Coppersmithが一般化したものです。

ヴィーデマンのアルゴリズム

を有限体F上の正方行列とし、を長さ のランダムベクトルとし、 とする。ベクトル に行列 を繰り返し掛け合わせることで得られるベクトル列を考える。を長さ の任意のベクトルとし、有限体元の列を考える。 ${\displaystyle M}$ ${\displaystyle n\times n}$ ${\displaystyle x_{\mathrm {base} }}$ ${\displaystyle n}$ ${\displaystyle x=Mx_{\mathrm {base} }}$ ${\displaystyle S=\left[x,Mx,M^{2}x,\ldots \right]}$ ${\displaystyle M}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]}$

行列 には最小多項式 があることが分かっています。ケーリー・ハミルトン定理により、この多項式の次数 ( と呼ぶ) は 以下であることが分かっています。 を例に挙げましょう。すると、行列 の最小多項式によって数列 が消滅し、したがって となります。 ${\displaystyle M}$ ${\displaystyle n_{0}}$ ${\displaystyle n}$ ${\displaystyle \sum _{r=0}^{n_{0}}p_{r}M^{r}=0}$ ${\displaystyle \sum _{r=0}^{n_{0}}y\cdot (p_{r}(M^{r}x))=0}$ ${\displaystyle S}$ ${\displaystyle S_{y}}$

しかし、Berlekamp–Masseyアルゴリズムを用いると、 となる数列を比較的効率的に計算できます。この数列は、構成上 を消滅させますが、実際には も消滅させることを期待しています。つまり、 となります。次に、 の初期定義を利用して とします。つまり、は の非ゼロ核ベクトルであることが期待されます。 ${\displaystyle q_{0}\ldots q_{L}}$ ${\displaystyle \sum _{i=0}^{L}q_{i}S_{y}[{i+r}]=0\;\forall \;r}$ ${\displaystyle y\cdot S}$ ${\displaystyle S}$ ${\displaystyle \sum _{i=0}^{L}q_{i}M^{i}x=0}$ ${\displaystyle x}$ ${\displaystyle M\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }=0}$ ${\displaystyle \sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }}$ ${\displaystyle M}$

ブロック・ヴィーデマン（またはコッパースミス・ヴィーデマン）アルゴリズム

コンピュータ上での疎行列演算の自然な実装により、マシンワード幅に等しい数のベクトルに対してシーケンスSを並列計算することが容易になります。実際、通常、その数のベクトルに対して計算する方が、1つのベクトルに対して計算するよりも時間がかかりません。複数のプロセッサがある場合は、すべてのコンピュータで異なる乱数ベクトルの集合に対してシーケンスSを並列計算できます。

ベルレカンプ・マッセイ法を一般化して小さな行列の列を生成すると、多数のベクトルに対して生成された列から、元の大きな行列の核ベクトルを生成できることがわかります。 を計算する必要があります。ただし、と は長さnのベクトルの列である必要があります。しかし、実際には を単位ベクトルの列として取り、各時刻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 }}$

不変係数の計算

ブロック・ヴィーデマン法は、行列の主不変因子、すなわちフロベニウス正規形の最大ブロックを計算するために用いられる。 と （ただし はサイズ の有限体）が与えられたとき、の主不変因子がで保存される確率は ${\displaystyle M\in F_{q}^{n\times n}}$ ${\displaystyle U,V\in F_{q}^{b\times n}}$ ${\displaystyle F_{q}}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle k<b}$ ${\displaystyle M}$ ${\displaystyle \sum _{i=0}^{2n-1}UM^{i}V^{T}x^{i}}$

${\displaystyle 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}}}$. ^[1]

参考文献

1. ハリソン, ギャビン; ジョンソン, ジェレミー; サンダース, B. デイビッド (2022年1月1日). 「ブロック・ヴィーデマン法における主要不変因子の確率解析」. Journal of Symbolic Computation . 108 : 98–116 . arXiv : 1803.03864 . doi :10.1016/j.jsc.2021.06.005. ISSN  0747-7171.

• Wiedemann, D.、「有限体上のスパース線形方程式の解法」、IEEE Trans. Inf. Theory IT-32、pp. 54-62、1986 年。

• D. Coppersmith, ブロックWiedemannアルゴリズムによるGF(2)上の同次線形方程式の解法, Math. Comp. 62 (1994), 333-350.

• Villard の 1997 年の研究レポート「行列多項式を使用した Coppersmith のブロック Wiedemann アルゴリズムの研究」(表紙はフランス語ですが、内容は英語です) は、妥当な説明です。

• Thomé の論文「ベクトル生成多項式の準二次計算とブロック Wiedemann アルゴリズムの改良」では、ベクトル生成多項式の計算に、より洗練されたFFTベースのアルゴリズムが使用されており、 i _max  =  j _{max = 4 を使用して 2} ⁶⁰⁷ −1 を法とする 484603×484603 の要素行列のカーネル ベクトルを計算し、その結果、 GF (2 ⁶⁰⁷ )体で離散対数を計算する実用的な実装について説明しています。

「https://en.wikipedia.org/w/index.php?title=Block_Wiedemann_algorithm&oldid=1302715384」より取得