Метод четырёх русских для умножения матриц

Дано две квадратных матрицы $A_{[n \times n]}$ и $B_{[n \times n]}$, состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю $2$.

Простое решение

Если мы будем считать произведение матриц $C = A \cdot B$ по определению($c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}$), то сложность работы алгоритма составит $O(n^3)$ — каждый из $n^2$ элементов результирующей матрицы $C$ вычисляется за время, пропорциональное $n$.

Сейчас будет показано, как немного уменьшить это время.

Сжатие матриц

Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины $k$ подсчитаем и запомним их скалярное произведение по модулю $2$.

Возьмём первую матрицу. разделим каждую её строку на куски размера $k$. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине $k$(последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу $A'_{n \times \lceil\frac{n}{k} \rceil}$.

Аналогично поступим с матрицей $B$, вместо строк деля столбцы. Получим матрицу $B'_{\lceil\frac nk\rceil\times n}$.

Теперь, если вместо произведения матриц $A$ и $B$ считать произведение новых матриц $A'$ и $B'$, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы $C$ будет получаться уже за время, пропорциональное $\lceil \frac nk \rceil$ вместо $n$, и время произведения матриц сократится с $O(n^3)$ до $O(n^2 \cdot\frac nk) = O(\frac{n^3}{k})$.

Оценка сложности алгоритма и выбор k

Оценим асимптотику данного алгоритма.

• Предподсчёт скалярных произведений работает за $O(2^{2k}k)$.
• Создание матриц $A'$ и $B'$ — $O(n^2)$
• Перемножение полученных матриц — $O(\frac{n^3}{k})$

Итого: $O(2^{2k}k) + O(\frac{n^3}{k})$. Выбрав $k = \log n$, получаем требуемую асимптотику $O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})$

Пример работы алгоритма

Рассмотрим работу алгоритма на примере перемножения двух матриц $A$ и $B$, где

$A =$ $\left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{array}\right)$ , $B =$ $\left(\begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right)$

$k = log_2 n = log_2 4 = 2$, то предподсчитаем все скалярные произведения:

Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа $00$, $01$, $10$, $11$. Ниже приведена таблица, в которой записаны все искомые произведения:

$\begin{tabular}{|c|c|c|c|c|} \hline & \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\ \hline \textbf{00} & 0 & 0 & 0 & 0 \\ \hline \textbf{01} & 0 & 1 & 0 & 1 \\ \hline \textbf{10} & 0 & 0 & 1 & 1 \\ \hline \textbf{11} & 0 & 1 & 1 & 0\\ \hline \end{tabular}$

Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы $A'$ и $B'$:

$A' =$ $\left(\begin{array}{cccc} 01 & 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right)$ , $B' =$ $\left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \end{array}\right)$

Перемножим эти матрицы по модулю два с использованием нашего предпосчета:

$C = A' \times B' =$ $\left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}\right)$

Матрица $C$ - искомая.

Литература

• Gregory V. Bard — Accelerating Cryptanalysis with the Method of Four Russians July 22, 2006. Страница 5