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

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

Алгоритм медного мастера [ править ]

Пусть будет квадратной матрицей над некоторым конечным полем F, пусть будет случайным вектором длины , и пусть . Рассмотрим последовательность векторов, полученную многократным умножением вектора на матрицу ; пусть будет любой другой вектор длины , и рассмотрим последовательность элементов конечного поля${\ displaystyle M}$${\ Displaystyle п \ раз п}$ ${\ displaystyle x _ {\ mathrm {base}}}$${\ displaystyle n}$${\ displaystyle x = Mx _ {\ mathrm {base}}}$${\ Displaystyle S = \ влево [х, Mx, M ^ {2} х, \ 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}}$

Но алгоритм Берлекампа – Месси позволяет относительно эффективно вычислять некоторую последовательность с . Мы надеемся, что эта последовательность, которая по конструкции аннигилирует , фактически аннигилирует ; так что у нас есть . Затем мы воспользуемся преимуществом начального определения to say и , надеюсь, ненулевого вектора ядра .${\ displaystyle q_ {0} \ ldots q_ {L}}$${\ displaystyle \ sum _ {я = 0} ^ {L} q_ {i} S_ {y} [{i + r}] = 0 \; \ forall \; r}$${\ displaystyle y \ cdot S}$${\ displaystyle S}$${\ displaystyle \ sum _ {я = 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 для другого набора случайных векторов параллельно на всех компьютерах.

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

Ссылки [ править ]

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

В статье Томе « Субквадратичное вычисление полиномов, генерирующих вектор и усовершенствование блочного алгоритма Видемана » используется более сложный алгоритм на основе БПФ для вычисления полиномов, генерирующих вектор, и описывается практическая реализация с i _max  =  j _max  = 4, используемая для вычисления ядра. вектор матрицы 484603 × 484603 элементов по модулю 2 ⁶⁰⁷ -1, и, следовательно, для вычисления дискретных логарифмов в поле GF (2 ⁶⁰⁷ ).