Метод Видемана-Копперсмита

{Автор - Участник:GKormakov}

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Видемана-Копперсмита был предложен Дугласом Видеманом в статье 1986 года . Алгоритм позволял получить решение системы линейных уравнений $Ax = b$ над полем GF(2) (в общем случае, над конечным полем GF(q)) в случае, когда матрица A являлась разреженной. В частности, совместный алгоритм Видемана-Копперсмита решал задачу поиска нетривиальных векторов из ядра матрицы $A$, т.е. нетривиальные решения уравнения $Ax = 0$

Стоит отметить, что алгоритм описывался для квадратной матрицы $A$, однако его легко можно обобщить на случай прямоугольной матрицы, переходя к матрице $A^T A$

Статья обосновывала корректность алгоритма, оценивала сложность вычислений, рассматривала разложения многочленов на множители и вычисление матричных полиномов. После выхода статьи сам метод не получил широкого применения, однако теоретические оценки и вспомогательные алгоритмы получили признание.

В рамках вычислений алгоритм является улучшенной версией алгоритма Копперсмита и алгоритма Монтгомери. В отличии от алгоритма Монтгомери имеет более эффективную реализацию на параллельных вычислительных системах - одним из главных отличий является меньший обмен данными между вычислительными узлами.

Алгоритм получил широкое применение в алгоритмах криптографии, в том числе, в алгоритме факторизации, использующего факторные базы

Использование стандартных методов Крылова (например, метода Ланцоша) не могли гарантировать условий на матрицу в GF(2), которые гарантировали сходимость, в связи с этим и были предложены перечисленные выше методы.

1.2 Математическое описание алгоритма

1.2.1 Метод Видемана

1.2.1.1 Невырожденный случай

Пусть $Ax = b, A\in\mathbb{F}_2^{n \times n}, b\in \mathbb{F}_2^n$ - согласованная СЛАУ с квадратной невырожденной матрицей.

$\begin{align} f(\lambda) = 1 + \sum_{i=1}^n f_i \lambda^i \end{align}$ - характеристический полином матрицы $A$ с коэффициентами $f_i\in\mathbb{F}_2$

По теореме Гамильтона-Кэли $f(A) = 0$, следовательно, $f(A)b = 0$. И, учитывая вид характеристической функции:

$\begin{align} b = \sum_{i=1}^n f_i A^i b = A(\sum_{i=1}^{n-1} f_{i+1}A^i b ) \end{align}$

Таким образом, если коэффициенты характеристического полинома известны, то единственное решение исследуемой системы можно найти как линейную комбинацию векторов Крылова: $\begin{align} x = \sum_{i=1}^{n-1} f_{i+1}A^i b \end{align}$

Но как искать эти коэффициенты? Для случая СЛАУ с разреженной матрицей Видеман предложил следующую идею: 1Выбрать случайный вектор $y \in \mathbb{F}_2^n$, тогда для $j = 0...n$ верны следующие соотношения:

$\begin{align} y^Tf(A)A^jb = y^T(\sum_{i=0}^{n} f_iA^i)A^jb = \sum_{i=0}^{n}(y^TA^{i+j}b)f_i = 0 \end{align}$

Пусть $\alpha_i = y^T A^ib \in \mathbb{F}_2, \forall i=0...n$, тогда верхняя система преобразуется в однородную СЛАУ:

$\begin{align} \sum_{i=0}^{n}\alpha_{i+j}f_i = 0 , j = 0...n \end{align}$

с матрицей $H_{ij}=\alpha_{i+j}$ порядка n + 1, имеющую ганкелеву структуру, что позволяет проще (за $O(n^2)$ - алгоритм Тренча) решать СЛАУ, поскольку матрица задаётся 2n + 1 параметрами. Если переставить строки матрицы $H$ в обратном порядке, то матрица станет теплицевой. Над GF(2) также известны быстрые алгоритмы решения СЛАУ (алгоритм Берлекампа - Масси)

1.2.1.2 Вырожденный случай

Для случая нахождения произвольного вектора из ядра матрицы $A$ идея Видемана применяется в следующем виде:

Поскольку $A$ теперь вырожденная, то характеристический полином будет выглядеть иначе (занулятся младшие коэффициенты):

$\begin{align} f(\lambda) = \lambda^s(\sum_{i=0}^{n-s} f_{i+s} \lambda^i), причём f_s \neq 0 \end{align}$

В этом случае выбираем произвольный вектор $x\in\mathbb{F}_2^n$ и находим вектор $\omega \in \mathbb{F}_2^n$: $\begin{align} \omega = (\sum_{i=0}^{n-s} f_{i+s} A^i)x \end{align}$

Т.к. размерность ядра матрицы $\sum_{i=0}^{n-s} f_{i+s} A^i$ не может быть больше n - 1, а размерность пространства $\mathbb{F}$ равна n, то с вероятностью 1/2 $\omega \neq 0$. Если же он равен 0, то выбираем другой x и ищем степень матрицы $A$: $A^\delta \omega \neq 0, а A^{\delta + 1} \omega = 0$, тогда $A^\delta \omega$ - искомый вектор из ядра.

Перепишем итоговый алгоритм Видемана для нахождения вектора из ядра A:

1. Выбираем случайные векторы $x, y \in \mathbb{F}_2^n$

2. $\forall s = 0, ... 2n$ вычисляем $\alpha_s = y^TA^sx$ и строим полином $a(x) = \sum\alpha_ix^i \textit{формальной}$ степени 2n

3. Характеристическому полиному $f(x)$ ставим в соответствие полином $\widetilde{f(x)} = x^n f(\frac{1}{x}), тогда f_i = \widetilde{f(x)}_{n-i}$ и

$\sum_{i=0}^n\alpha_{i+j}f_i = \sum_{i=0}^n\alpha_{i+j}\widetilde{f(x)}_{n-i} = 0, j=0...n$, т.е. все коэффициенты в $a(x)\widetilde{f(x)}$ при $x^n, x^{n+1}, ..., x^{2n}$ будут равны 0.

Т.е. $a(x)\widetilde{f(x)} = g(x) mod \,x^{2n + 1}, где\, deg(g) \lt n$

Таким образом построили полином $\widetilde{f(x)}$

4. Получаем решение $\omega = A^\delta \sum_if_iA^ix : A\omega = 0$ алгоритмом, описанным выше

1.2.2 Алгоритм Видемана-Копперсмита

Алгоритм Видемана по поиску вектора из ядра матрицы A сводился к решению СЛАУ с генкелевой или теплицевой матрицей, что ускоряло алгоритм, однако алгоритм Видемана является последовательным алгоритмом (коэффициенты полинома $a(x)$ вычисляются последовательно), т.е. он не имеет выигрыша по скорости перед методом Монтгомери при распараллеливании на несколько узлов. Поэтому Копперсмит добавил в алгоритм Видемана работу с блочными матрицами.

2 Литература

<references \>