Алгоритм Видемана — алгоритм, позволяющий получить решение системы линейных уравнений над конечным полем . Был предложен Дугласом Видеманом () в 1986 году. В течение некоторого времени после опубликования статьи, алгоритм не получил большой поддержки и считался пригодным только для получения наилучших оценок сложности. Но позже алгоритмы Видемана были реализованы на компьютере и использовались, например, для поиска разложения многочленов на множители над конечными полями.
История возникновения Алгоритмы Видемана были представлены общественности в прошлом столетии. В 1986 году в январском выпуске журнала IEEE Transactions on Information Theory была опубликована статья Дугласа Видемана под названием «Решение разреженной системы линейных уравнений над конечным полем» (). В ней были описаны алгоритмы для решения системы линейных уравнений над конечным полем в случае когда матрица системы является разреженной. Причём в статье были рассмотрены случаи с различными разреженными матрицами. Также в статье было опубликовано обоснование алгоритмов и оценка сложности их работы.
Задача Алгоритм нужен чтобы решить систему линейных уравнений . Матрица имеет размерность и предполагается разреженной, количество ненулевых элементов в ней равно .
Теория С помощью матрицы определяется невырожденное линейное отображение(которое обозначается также ) на пространстве . Рассматривается пространство , порождённое множеством векторов и определяется - линейное отображение на .
Обозначим — минимальный многочлен , то есть ненулевой многочлен наименьшей степени, такой, что является нулевым отображением , при чём нормализованный так, что его свободный член равен единице. Отметим, что если , то - нулевое отображение тогда и только тогда, когда . Кроме того, делит многочлен , и поэтому .
Обозначим , где - коэффициенты . Если можно найти , то решение системы также находится: так как и , то
Пусть - какой-либо фиксированный вектор из . Обозначим стандартное билинейное отображение в как , то есть .
Так как , то последовательность
удовлетворяет линейному рекуррентному соотношению, характеристический многочлен которого равен . Пусть - характеристический многочлен самого короткого рекуррентного соотношения. Тогда . Действительно, если разделить с остатком
,
то из равенств
,
и минимальности будет следовать, что . Поскольку свободный член равен единице, то можно принять, что свободный член равен единице.
Минимальный многочлен для последовательности может быть получен с помощью алгоритма Берлекэмпа-Месси по первым её членам. Существуют два метода решения исходной системы.
Первый метод. Выбирается случайный вектор . Строится и в предположении, что , находится по формуле
Этим путём с достаточно высокой вероятностью можно найти решение.
Второй метод. Пусть для некоторого вектора . Если вектор равен 0, то находится по формуле
(так как тогда ).
Если же , то повторяется процедура, то есть выбирается случайный вектор и строится минимальный многочлен для последовательности . Если , то и можно найти решение x по формуле
,
иначе выбирается и так далее.
Докажем, что если сделано итераций, то делит . Выше было показано, что . Далее, если предположить что делит , то поскольку - минимальный многочлен для последовательности , а многочлен её аннулирует, то , что и требовалось доказать.
Теперь очевидно, что если , то . То есть, как только будет найден нулевой вектор , то можно найти решение исходной системы по формуле
.
Алгоритм 1 В оригинальной статье алгоритм имеет такое название. На его основе строится детерминированный алгоритм, который в оригинальной статье называется алгоритм 2.
Описание алгоритма
1 этап. Приравнивается .
2 этап. Если , то решение равно , и алгоритм прекращает работу.
3 этап. Выбирается случайный вектор .
4 этап. Вычислить первые членов последовательности .
5 этап. Вычислить минимальный многочлен последовательности из 4-го этапа, причём нормализовать его так, чтобы его свободный член равнялся единице. Это можно осуществить с помощью алгоритма Берлекэмпа-Месси.
6 этап. Присвоить
, где
,
.
7 этап. Присвоить и вернуться на второй этап.
Обоснование корректности алгоритма с помощью метода математической индукции
соответствует правой части формулы без знака минус. При выбирается , рассматривается членов последовательности и находится по алгоритму Берлекэмпа-Месси. Тогда .
Пусть после проходов алгоритма выполнены равенства
Тогда после прохода
,
То есть формулы для и сохраняются. Теперь корректность алгоритма следует из раздела теория.
Детерминированный алгоритм Описание алгоритма
1 этап. Найти значение .
2 этап. Приравнять нулю , а единице.
3 этап. Присвоить (единица находится на месте).
4 этап. Найти последовательность при помощи первого этапа.
5 этап. Найти последовательность , можно использовать дискретное преобразование Фурье.
6 этап. Найти минимальный многочлен со свободным членом равным единице с помощью алгоритма Берлекэмпа-Месси.
7 этап. Присвоить .
8 этап. Увеличить на единицу. Если и , то возвратиться на 3 этап.
9 этап. Для многочлена с помощью найденных на первом этапе значений отыскать решение системы с помощью формулы
.
Обоснование корректности алгоритма
Обратим внимание, что фактически алгоритм работает также, как и алгоритм 1, только векторы выбираются не случайно, а идёт перебор единичных векторов . Очевидно, что , где — минимальный многочлен для последовательности
.
Алгоритм закончил работу при некотором значении параметра . Предположим, что . Так как и , то . Отсюда следует, что на этапе 9 решение исходной системы точно будет найдено.
Теперь рассмотрим случай . Поскольку был совершён перебор всех единичных векторов , то вектор ортогонален . Следовательно, . Так как и -минимальный многочлен, то . Поэтому и в данном случае подтверждена корректность работы алгоритма.
Оценка сложности алгоритма Для детерминированного алгоритма Видеманом была получена следующая оценка сложности: . Полученная оценка сложности является наилучшей среди известных. Благодаря алгоритму Видемана возможно улучшение оценки сложности в других алгоритмах, использующих методы решения линейных систем.
Аналогичные алгоритмы Где может пригодится решение системы линейных уравнений над конечным полем? Потребность в их решении возникает при использовании алгоритмов факторизации и при решении задач дискретного логарифмирования, использующих факторные базы. Существует большое количество алгоритмов для получения решения системы линейных уравнений над конечными полями. Помимо алгоритмов Видемана можно использовать гауссово и структурное гауссово исключения, алгоритм Ланцоша, метод сопряжённых градиентов . Также известны алгоритмы основанные на быстром умножении матриц, например на алгоритмах Штрассена и Копперсмита-Винограда. Свои алгоритмы были предложены Коновальцевым и Бриллхартом.
В общем случае (матрица системы не является разреженной) в последнее время чаще используется алгоритм Ланцоша(вероятно, вместе со структурированным гауссовым исключением для получения более плотной матрицы подсистемы). Но в случае разреженной матрицы эффективнее всего использовать алгоритмы Видемана, так как оценки их сложности являются наилучшими из известных. Не сразу алгоритмы Видемана получили признание, но позже всё-таки были реализованы на компьютере. Алгоритмы использовались, например, для разложения многочленов на множители над конечными полями.
Позже появились различные модификации оригинального алгоритма, например блочный алгоритм Видемана.
Примечания
Литература
Категория:Криптография Категория:Теоретико-числовые алгоритмы