Матрица <tex> C </tex> - искомая.
== Код алгоритма ==
<code>
// Чтение матриц
for i := 0 to n - 1
for j := 0 to n - 1 {
read(cur);
a[i][j] = cur;
}
for i := 0 to n - 1
for j := 0 to n - 1 {
read(cur);
b[i][j] = cur;
}
// Предподсчёт скалярных произведений
// Пусть preСalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j
// "&" - битовый and; "**" - возведение в степень.
int k = ceil(log2(n)); //округление вверх
for i := 0 to (2 ** k) - 1
for j := 0 to (2 ** k) - 1 {
int scalMul = 0;
for pos := 0 to k - 1
if (((2 ** pos) & i) != 0 and ((2 ** pos) & j) != 0) {
scalMul = (scalMul + 1) mod 2;
}
preСalc[i][j] = scalMul;
}
// Создание сжатых матриц anew, bnew
for i := 0 to n - 1 {
while (start < n) {
int curSumA = 0, curSumB = 0, curPos = start, deg = (2 ** (k - 1));
while (curPos < start + k and curPos < n) {
curSumA = curSumA + a[i][curPos] * deg;
curSumB = curSumB + b[curPos][i] * deg;
deg = deg div 2;
curPos = curPos + 1;
}
anew[i][start div k] = curSumA;
bnew[start div k][i] = curSumB;
start = start + k;
}
}
//Перемножение полученных матриц
for i := 0 to n - 1
for j := 0 to n - 1 {
int curAns = 0;
for pos := 0 to m - 1 {
curAns = (curAns + preСalc[anew[i][pos]][bnew[pos][j]]) mod 2;
}
ans[i][j] = curAns;
}
// Вывод ответа
for i := 0 to n - 1
for j := 0 to n - 1 {
write(ans[i][j]);
}
writeln();
}
</code>
== Литература ==
* ''Gregory V. Bard'' — '''Accelerating Cryptanalysis with the Method of Four Russians'''
