Блочный алгоритм Видемана - Block Wiedemann algorithm

В блочный алгоритм Видемана для вычисления векторов ядра матрица над конечным полем является обобщением алгоритма благодаря Дон Копперсмит.

Алгоритм Копперсмита

Позволять ${\displaystyle M}$ быть ${\displaystyle n\times n}$ квадратная матрица над некоторыми конечное поле F, пусть ${\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}}$.

Но Алгоритм Берлекампа-Месси позволяет относительно эффективно вычислять некоторую последовательность ${\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 параллельно для числа векторов, равного ширине машинного слова - действительно, обычно для этого количества векторов требуется не больше вычислений, чем для одного. Если у вас несколько процессоров, вы можете вычислить последовательность S для другого набора случайных векторов параллельно на всех компьютерах.

Оказывается, обобщив алгоритм Берлекампа – Месси для получения последовательности малых матриц, можно взять последовательность, созданную для большого количества векторов, и сгенерировать вектор ядра исходной большой матрицы. Вам нужно вычислить ${\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}}$ - серия векторов длины n; но на практике вы можете взять ${\displaystyle y_{i}}$ как последовательность единичных векторов и просто выпишите первый ${\displaystyle i_{\max }}$ записи в ваших векторах каждый раз т.

Рекомендации

Отчет об исследовании Вилларда 1997 г. 'Исследование блочного алгоритма Видемана Копперсмита с использованием матричных полиномов '(обложка на французском языке, но содержание на английском языке) является разумным описанием.

Бумага Томе 'Субквадратичное вычисление векторных полиномов и усовершенствование блочного алгоритма Видемана 'использует более сложный БПФ основанный на алгоритме вычисления векторных полиномов, и описывает практическую реализацию с я_{Максимум} = j_{Максимум} = 4 используется для вычисления вектора ядра матрицы 484603 × 484603 элементов по модулю 2⁶⁰⁷−1, и, следовательно, для вычисления дискретных логарифмов в поле GF(2⁶⁰⁷).