Алгоритм Видемана

Алгоритм Видемана — алгоритм, позволяющий получить решение системы линейных уравнений $Ax=b,b\neq 0$ над конечным полем $K=GF(q)$. Был предложен Дугласом Видеманом (англ. Douglas Wiedemann) в 1986 году. В течение некоторого времени после опубликования статьи, алгоритм не получил большой поддержки и считался пригодным только для получения наилучших оценок сложности. Но позже алгоритмы Видемана были реализованы на компьютере и использовались, например, для поиска разложения многочленов на множители над конечными полями.

История возникновения

Алгоритмы Видемана были представлены общественности в прошлом столетии. В 1986 году в январском выпуске журнала IEEE Transactions on Information Theory была опубликована статья Дугласа Видемана под названием «Решение разреженной системы линейных уравнений над конечным полем» (англ. Solving sparse linear equations over finite fields). В ней были описаны алгоритмы для решения системы линейных уравнений над конечным полем в случае когда матрица системы является разреженной. Причём в статье были рассмотрены случаи с различными разреженными матрицами. Также в статье было опубликовано обоснование алгоритмов и оценка сложности их работы.

Задача

Алгоритм нужен чтобы решить систему линейных уравнений $Ax=b,b\neq 0$. Матрица $A$ имеет размерность $n\times n$ и предполагается разреженной, количество ненулевых элементов в ней равно $w$.

Теория

С помощью матрицы $A$ определяется невырожденное линейное отображение(которое обозначается также $A$) на пространстве $\mathrm {K} ^{n}$. Рассматривается пространство $S$, порождённое множеством векторов $\left\{{(A^{i}b_{k})}\right\}_{i=0,1,2}$ и определяется $A_{S}=A|_{S}$ - линейное отображение $S$ на $S$.

Обозначим $f_{z}\in \mathrm {K} ^{n}$ — минимальный многочлен $A_{S}$, то есть ненулевой многочлен наименьшей степени, такой, что $f(A_{s})$ является нулевым отображением $S$, при чём нормализованный так, что его свободный член равен единице. Отметим, что если $g(z)\in \mathrm {K} [z]$, то $g(A_{s})$ - нулевое отображение тогда и только тогда, когда $g(A)b=0$. Кроме того, $f(z)$ делит многочлен $det(zl_{n}-A)$, и поэтому $degf(z)\leqslant n$.

Обозначим $d=degf(z),f(z)=\sum _{i=0}^{d}{f[i]z^{i}}$, где $f[i]\in \mathrm {K} ^{n}$ - коэффициенты $f(z)$. Если можно найти $f(z)$, то решение системы $Ax=b,b\neq 0$ также находится: так как $f(A)b=0$ и $f[0]=1$, то

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$

Пусть $u$ - какой-либо фиксированный вектор из $\mathrm {K} ^{n}$. Обозначим стандартное билинейное отображение $\mathrm {K} ^{n}$ в $\mathrm {K}$ как $(,)$ , то есть $((v_{1},...,v_{n}),(w_{1},...,w_{n}))=\sum _{i=1}^{n}{v_{i}w_{i}}$.

Так как $f(A)b=0$, то последовательность

$(u,A^{i}b),i=0,1,2,...,$

удовлетворяет линейному рекуррентному соотношению, характеристический многочлен которого равен $f(z)$. Пусть $f_{u}(z)$ - характеристический многочлен самого короткого рекуррентного соотношения. Тогда $f(z)|f_{u}(z)$. Действительно, если разделить с остатком

$f(z)=q(z)f_{u}(z)+r(z)$, $degr(z)<deg~f_{u}(z)$

то из равенств

$0=(u,f(A)b)=(u,q(A)f_{u}(A)b)+(u,r(A)b)$,

$(u,f_{u}(A)A^{j}b)=0,j=0,1,2,...,$

и минимальности $f_{u}(z)$ будет следовать, что $r(z)=0$. Поскольку свободный член $f(z)$ равен единице, то можно принять, что свободный член $f_{u}(z)$ равен единице.

Минимальный многочлен $f_{u}(z)$ для последовательности $(u,A^{i}b),i=0,1,2,...,$ может быть получен с помощью алгоритма Берлекэмпа-Месси по первым её $2n$ членам. Существуют два метода решения исходной системы.

Первый метод. Выбирается случайный вектор $u(z)$. Строится $f_{u}(z)$ и в предположении, что $f(z)=f_{u}(z)$, находится $x$ по формуле

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$

Этим путём с достаточно высокой вероятностью можно найти решение.

Второй метод. Пусть $b_{0}=b,f_{1}(z)=f_{u_{1}}(z)$ для некоторого вектора $u_{1}$ . Если вектор $b_{1}=f_{1}(A)b_{0}$ равен 0, то находится $x$ по формуле

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ (так как тогда $f_{1}(z)=f(z)$ ).

Если же $b_{1}\neq 0$, то повторяется процедура, то есть выбирается случайный вектор $u_{2}$ и строится минимальный многочлен $f_{2}(z)=f_{u_{2}}(z)$ для последовательности $(u_{2},A_{i}b_{1})$. Если $b_{2}=f_{2}(A)b_{1}=0$, то $f(z)=f_{1}(z)f_{2}(z)$ и можно найти решение x по формуле

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$,

иначе выбирается $u_{3}$ и так далее.

Докажем, что если сделано $k$ итераций, то $f_{1}(z)...f_{k}(z)$ делит $f(z)$. Выше было показано, что $f-1(z)|f(z)$. Далее, если предположить что $f_{1}(z)...f_{k-1}(z)$ делит $f(z)$, то поскольку $f_{k}(z)$ - минимальный многочлен для последовательности $\left\{(u_{k},A^{i}b_{k-1})\right\}_{i}=\left\{(u_{k},f_{k-1}(A)...f_{1}(A^{j})b)\right\}_{j}$, а многочлен ${\frac {f(z)}{f_{1}(z)...f_{k-1}(z)}}$ её аннулирует, то ${f_{k}(z)}|{\frac {f(z)}{f_{1}(z)...f_{k-1}(z)}}$, что и требовалось доказать.

Теперь очевидно, что если $b_{x}=f_{k}(A)...f_{1}(A)b=0$, то $f(x)=f_{1}(x)...f_{k}(x)$. То есть, как только будет найден нулевой вектор $b_{k}=f_{k}(A)b_{k-1}$, то можно найти решение исходной системы по формуле

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$.

Алгоритм 1

В оригинальной статье алгоритм имеет такое название. На его основе строится детерминированный алгоритм, который в оригинальной статье называется алгоритм 2.

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

1 этап. Приравнивается $b_{0}=b,k=0,y_{0}=0,d_{0}=0$.

2 этап. Если $b_{k}=0$, то решение равно $x=-y_{k}$, и алгоритм прекращает работу.

3 этап. Выбирается случайный вектор $u_{k+1}\in \mathrm {K} ^{n},u_{k+1}\neq 0$.

4 этап. Вычислить первые $2(n-d_{k})$ членов последовательности $\left\{{(u_{k+1},A^{i}b_{k})}\right\}_{i=0}^{\infty }$.

5 этап. Вычислить минимальный многочлен $f_{k+1}(z)$ последовательности из 4-го этапа, причём нормализовать его так, чтобы его свободный член равнялся единице. Это можно осуществить с помощью алгоритма Берлекэмпа-Месси.

6 этап. Присвоить

$y_{k+1}=y_{k}+{\hat {f}}_{k+1}(A)b_{k}$, где ${\hat {f}}(z)={\frac {f(z)-f(0)}{z}}$

$b_{k+1}=b_{0}+Ay_{k+1}$,

$d_{k+1}=d_{k}+deg~f_{k+1}(z)$.

7 этап. Присвоить $k=k+1$ и вернуться на второй этап.

Обоснование корректности алгоритма с помощью метода математической индукции

${\hat {f}}(z)={\frac {f(z)-f(0)}{z}}$ соответствует правой части формулы $x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$ без знака минус. При $k=0$ выбирается $u_{1}$, рассматривается $2n$ членов последовательности $\left\{{(u_{1},A^{i}b_{0})}\right\}_{i=0,1,2}$ и находится $f_{1}(x)$ по алгоритму Берлекэмпа-Месси. Тогда $y_{1}={\hat {f}}_{1}(A)b,b_{1}=b_{0}+Ay_{1}=b+A{\frac {f_{1}(A)-1}{A}}b=f_{1}(A)b,d_{1}=degf_{1}(z)$.

Пусть после $k$ проходов алгоритма выполнены равенства

$y_{k}={\frac {f_{k}(A)...f_{1}(A)-1}{A}}b$

$b_{k}=f_{k}(A)...f_{1}(A)b$

Тогда после $k+1$ прохода

$y_{k+1}=y_{k}+{\hat {f}}_{k+1}(A)b_{k}={\frac {f_{k}(A)...f_{1}(A)-1}{A}}b+{\frac {f_{k+1}(A)-1}{A}}f_{k}(A)...f_{1}(A)b={\frac {f_{k+1}(A)...f_{1}(A)-1}{A}}b$,

$b_{k+1}=b_{k}+A{\frac {f_{k+1}(A)...f_{1}(A)-1}{A}}b=f_{k+1}(A)...f_{1}(A)b$

То есть формулы для $y_{k}$ и $b_{k}$ сохраняются. Теперь корректность алгоритма следует из раздела теория.

Детерминированный алгоритм

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

1 этап. Найти значение $A^{i}b,i=0,1,...,2n-1$.

2 этап. Приравнять нулю $k$, а $g_{0}(z)$ единице.

3 этап. Присвоить $u_{k+1}=(0,...,0,1,0,...,0)$(единица находится на $k+1$ месте).

4 этап. Найти последовательность $(u_{k+1},A^{i}b),i=0,1,...,2n-1$ при помощи первого этапа.

5 этап. Найти последовательность $(u_{k+1},g_{k}(A)A^{i}b),i=0,1,...,2n-1-deg~g_{k}(z)$, можно использовать дискретное преобразование Фурье.

6 этап. Найти минимальный многочлен $f_{k+1}(z)$ со свободным членом равным единице с помощью алгоритма Берлекэмпа-Месси.

7 этап. Присвоить $g_{k+1}(z)=f_{k+1}(z)g_{k}(z)$.

8 этап. Увеличить $k$ на единицу. Если $deg~g_{k}(z)<n$ и $k<n$, то возвратиться на 3 этап.

9 этап. Для многочлена $f(z)=g_{k}(z)$ с помощью найденных на первом этапе значений $A^{i}b$ отыскать решение $x$ системы с помощью формулы

$x=-\sum _{i=1}^{d}{f[i]A^{i-1}b}$.

Обоснование корректности алгоритма

Обратим внимание, что фактически алгоритм работает также, как и алгоритм 1, только векторы $u_{k}$ выбираются не случайно, а идёт перебор единичных векторов $(0,...,0,1,0,...,0)$. Очевидно, что $g_{k}(z)=f_{k}(z)...f_{1}(z)$, где $f_{k}(z)$ — минимальный многочлен для последовательности

$(u_{k},f_{k-1}(A)...f_{1}(A)A^{i}b),i=0,1,...,2n-1-deg(f_{k-1}...f_{1})$.

Алгоритм закончил работу при некотором значении параметра $k$. Предположим, что $k<n,deg~g_{k}(z)=n$. Так как $deg~f(z)\leqslant n$ и $g_{k}(z)|f(z)$, то $g_{k}(z)=f(z)$. Отсюда следует, что на этапе 9 решение исходной системы точно будет найдено.

Теперь рассмотрим случай $k=n$. Поскольку был совершён перебор всех единичных векторов $u_{1},...,u_{n}$, то вектор $g_{n}(A)b$ ортогонален $u_{1},...,u_{n}$. Следовательно, $g_{n}(A)b=0$. Так как $g_{n}(z)|f(z)$ и $f(z)$ -минимальный многочлен, то $g_{k}(z)=f(z)$. Поэтому и в данном случае подтверждена корректность работы алгоритма.

Оценка сложности алгоритма

Для детерминированного алгоритма Видеманом была получена следующая оценка сложности: $O(n(w+n~log(n)log(log(n))))$. Полученная оценка сложности является наилучшей среди известных. Благодаря алгоритму Видемана возможно улучшение оценки сложности в других алгоритмах, использующих методы решения линейных систем.

Аналогичные алгоритмы

Где может пригодится решение системы линейных уравнений над конечным полем? Потребность в их решении возникает при использовании алгоритмов факторизации и при решении задач дискретного логарифмирования, использующих факторные базы. Существует большое количество алгоритмов для получения решения системы линейных уравнений над конечными полями. Помимо алгоритмов Видемана можно использовать гауссово и структурное гауссово исключения, алгоритм Ланцоша, метод сопряжённых градиентов . Также известны алгоритмы основанные на быстром умножении матриц, например на алгоритмах Штрассена и Копперсмита-Винограда. Свои алгоритмы были предложены Коновальцевым и Бриллхартом.

В общем случае (матрица системы не является разреженной) в последнее время чаще используется алгоритм Ланцоша(вероятно, вместе со структурированным гауссовым исключением для получения более плотной матрицы подсистемы). Но в случае разреженной матрицы эффективнее всего использовать алгоритмы Видемана, так как оценки их сложности являются наилучшими из известных. Не сразу алгоритмы Видемана получили признание, но позже всё-таки были реализованы на компьютере. Алгоритмы использовались, например, для разложения многочленов на множители над конечными полями.

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

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Wiedemann D.H. Solving sparce linear equations over finite fields (англ.). — 1986. — Январь (т. 32, № 1). — С. 54—62.
• Kaltofen E.,Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm (англ.) // Proceedings of ISSAC’94. — 1994. — С. 90—98.
• Massey J. L. Shift-register synthesis and BCH decoding (англ.) // IEEE Trans. Inform. Theory. — 1969. — Т. 15. — С. 122—127.
• Алексеев В. Б. Сложность умножения матриц. Обзор (рус.) // Кибернетич. сборн.. — 1988. — Т. 25. — С. 189-236.

• Коновальцев И.В. Об одном алгоритме решения систем линеных уравнений в конечных полях (рус.) // Проблемы кибернетики. — 1967. — Т. 16. — С. 269-274.
• Brillhart J. A note on finding depencensies over GF(2) (англ.) // Utilitas Math. — 1989. — Т. 36. — С. 211-213.
• LaMacchia B., Odlyzko A. Solving large sparse linear systems over finite fields (англ.) // Advances in Cryptology—CRYPTO’90. — 1990. — Т. 537. — С. 109-113.
• Coppersmith D., Odlyzko A., Schroeppel R. Discrete logarithms in GF(p) (англ.) // Algorithmica. — 1986. — Т. 1. — С. 1-15.