Метод Видемана-Копперсмита: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 100: Строка 100:
 
====Алгоритм Видемана-Копперсмита====
 
====Алгоритм Видемана-Копперсмита====
 
Алгоритм Видемана по поиску вектора из ядра матрицы A сводился к решению СЛАУ с генкелевой или теплицевой матрицей, что ускоряло алгоритм, однако алгоритм Видемана является последовательным алгоритмом (коэффициенты полинома <math>a(x)</math> вычисляются последовательно), т.е. он не имеет выигрыша по скорости перед методом Монтгомери при распараллеливании на несколько узлов. Поэтому Копперсмит добавил в алгоритм Видемана работу с блочными матрицами.
 
Алгоритм Видемана по поиску вектора из ядра матрицы A сводился к решению СЛАУ с генкелевой или теплицевой матрицей, что ускоряло алгоритм, однако алгоритм Видемана является последовательным алгоритмом (коэффициенты полинома <math>a(x)</math> вычисляются последовательно), т.е. он не имеет выигрыша по скорости перед методом Монтгомери при распараллеливании на несколько узлов. Поэтому Копперсмит добавил в алгоритм Видемана работу с блочными матрицами.
 +
 +
=== Вычислительное ядро алгоритма ===
 +
 +
 +
=== Макроструктура алгоритма ===
 +
 +
 +
=== Схема реализации последовательного алгоритма ===
 +
 +
 +
=== Последовательная сложность алгоритма ===
 +
 +
 +
=== Информационный граф ===
 +
 +
 +
=== Ресурс параллелизма алгоритма ===
 +
 +
=== Входные и выходные данные алгоритма ===
 +
 +
 +
=== Свойства алгоритма ===
 +
 +
 +
== Программная реализация алгоритма ==
 +
 +
 +
=== Особенности реализации последовательного алгоритма ===
 +
 +
 +
=== Локальность данных и вычислений ===
 +
 +
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
 +
 +
 +
=== Масштабируемость алгоритма и его реализации ===
 +
 +
 +
=== Динамические характеристики и эффективность реализации алгоритма ===
 +
 +
 +
=== Выводы для классов архитектур ===
 +
 +
 +
=== Существующие реализации алгоритма ===
 
== Литература ==
 
== Литература ==
  
 
<references \>
 
<references \>

Версия 03:24, 22 октября 2019

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math] \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} [/math]

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

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

[math] \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} [/math]

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

[math] \begin{align} \sum_{i=0}^{n}\alpha_{i+j}f_i = 0 , j = 0...n \end{align} [/math]

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

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

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

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

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

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

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

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

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

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

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

[math]\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[/math], т.е. все коэффициенты в [math]a(x)\widetilde{f(x)}[/math] при [math]x^n, x^{n+1}, ..., x^{2n}[/math] будут равны 0.

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

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

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

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

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

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

<references \>

  1. Wiedemann D.H. Solving sparce linear equations over finite fields (англ.). — 1986. — Январь (т. 32, № 1). — С. 54—62.
  2. Замарашкин, Николай Леонидович. Алгоритмы для разряженных систем линейных уравнений в GF(2) [Текст] : учебное пособие для студентов высших учебных заведений, обучающихся по направлениям ВПО 010400 "Прикладная математика и информатика" и 010300 "Фундаментальная информатика и информационные технологии" / Н. Л. Замарашкин ; Московский гос. ун-т им. М. В. Ломоносова. - Москва : Изд-во Московского ун-та, 2013. - 128, [2] с. : ил., табл.; 21 см. - (Серия: Суперкомпьютерное образование / Суперкомпьютерный консорциум ун-тов России).; ISBN 978-5-211-06483-6