Метод четырёх русских для умножения матриц — различия между версиями
Строка 44: | Строка 44: | ||
// Предподсчёт скалярных произведений | // Предподсчёт скалярных произведений | ||
− | // Пусть precalc[ | + | // Пусть precalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j |
− | k = log n | + | int k = ceil(log n); //округление вверх |
− | for | + | for i := 0 to (1 << k) - 1 |
− | for | + | for j := 0 to (1 << k) - 1 { |
− | + | int scalmul = 0; | |
− | + | for pos := 0 to k - 1 | |
+ | if (((1 << pos) & i) != 0 && ((1 << pos) & j) != 0) { | ||
+ | scalmul = (scalmul + 1) % 2; | ||
+ | } | ||
+ | precalc[i][j] = scalmul; | ||
} | } | ||
// Создание сжатых матриц | // Создание сжатых матриц | ||
Строка 65: | Строка 69: | ||
} | } | ||
//Перемножение полученных матриц | //Перемножение полученных матриц | ||
− | for | + | for i := 0 to n - 1 |
− | for | + | for j := 0 to n - 1 { |
− | + | int curans = 0; | |
− | + | for pos := 0 to m - 1 { | |
− | + | curans = (curans + precalc[anew[i][pos]][bnew[pos][j]]) % 2; | |
+ | } | ||
+ | ans[i][j] = curans; | ||
+ | } | ||
+ | |||
</code> | </code> |
Версия 06:20, 21 декабря 2011
Рассмотрим следующую задачу: «Дано две квадратных матрицы
и , состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю .»Содержание
Простое решение
Если мы будем считать произведение матриц
по определению( ), то трудоёмкость алгоритма составит — каждый из элементов результирующей матрицы вычисляется за время, пропорциональное .Сейчас будет показано, как немного уменьшить это время.
Сжатие матриц
Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины
подсчитаем и запомним их скалярное произведение по модулю .Возьмём первую матрицу. разделим каждую её строку на куски размера
. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине (последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу .Аналогично поступим с матрицей
, вместо строк деля столбцы. Получим матрицу .Теперь, если вместо произведения матриц
и считать произведение новых матриц и , воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы будет получаться уже за время, пропорциональное вместо , и время произведения матриц сократится с до .Оценка трудоёмкости и выбор k
Оценим трудоёмкость данного алгоритма.
- Предподсчёт скалярных произведений работает за .
- Создание матриц и —
- Перемножение полученных матриц —
Итого:
. Приведем анализ выбора числа для получения оптимальной сложности алгоритма.В силу возрастания функции
и убывания функции имеем, что сложность будет оптимальна при таком значении , что . Прологарифмируем обе части этого равенства:
В силу того, что
пренебрежительно мал по сравнению с имеем, что с точностью до константы равенТаким образом, при подстановке
, получаем итоговую трудоёмкостьКод алгоритма
// Предподсчёт скалярных произведений // Пусть precalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j int k = ceil(log n); //округление вверх for i := 0 to (1 << k) - 1 for j := 0 to (1 << k) - 1 { int scalmul = 0; for pos := 0 to k - 1 if (((1 << pos) & i) != 0 && ((1 << pos) & j) != 0) { scalmul = (scalmul + 1) % 2; } precalc[i][j] = scalmul; } // Создание сжатых матриц for I = 0 to n - 1 { для всех стартовых позиций start группы из k элементов { Представляем текущую двоичную последовательность в текущей строке I матрицы A как десятичное число. Записываем полученное значение в A'. } } for J = 0 to n - 1 { для всех стартовых позиций start группы из k элементов { Представляем текущую двоичную последовательность в текущем столбце J матрицы B как десятичное число. Записываем полученное значение в B'. } } //Перемножение полученных матриц for i := 0 to n - 1 for j := 0 to n - 1 { int curans = 0; for pos := 0 to m - 1 { curans = (curans + precalc[anew[i][pos]][bnew[pos][j]]) % 2; } ans[i][j] = curans; }
Литература
- Gregory V. Bard — Accelerating Cryptanalysis with the Method of Four Russians