Как вычислить обратную ключевую матрицу в алгоритме Шифра Выступа?
Мы можем сделать это следующим образом:
Поддерживая массив sum, который по индексу ith содержит сумму модулей от 0 до ith.
Для каждого индекса ith нам нужно найти максимальную субсумму, заканчивающуюся этим индексом:
Для каждого подмассива (start + 1, i) мы знаем, что мод-сумма этого субмарина массив
int a = (sum[i] - sum[start] + M) % M
Таким образом, мы можем получить субсумму больше, чем sum[i], если sum[start] больше, чем sum[i] и так близко к sum[i], как возможно.
Это можно легко сделать, если вы используете двоичное дерево поиска.
Псевдокод:
int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
sum[i] = sum[i - 1] + A[i];
sum[i] %= M;
int a = tree.getMinimumValueLargerThan(sum[i]);
result = max((sum[i] - a + M) % M, result);
tree.add(sum[i]);
}
print result;
Сложность по времени: O (n log n)
1 ответ
Вы должны изучить теорему линейного сравнения и расширенный алгоритм GCD , которые относятся к теории чисел , чтобы понять математику, лежащую в основе арифметический по модулю .
Матрица K, обратная, например, (1 / det (K)) * adjoint (K), где det (K) <> 0.
Я предполагаю, что вы не понимаете, как вычислить 1 / det (K) в арифметике по модулю, и здесь в игру вступают линейные сравнения и НОД.
Ваш K имеет det (K) = -121. Допустим, модуль m равен 26. Мы хотим x * (- 121) = 1 (mod 26).
[a = b (mod m) означает, что ab = N * m]
Мы можем легко найти, что для x = 3 вышеупомянутое сравнение верно, потому что 26 делит (3 * (- 121) -1) в точности. Конечно, правильный способ - использовать GCD в обратном порядке для вычисления x, но у меня нет времени объяснять, как это сделать. Проверьте расширенный алгоритм GCD:)
Теперь inv (K) = 3 * ([3-8], [-17 5]) (mod 26) = ([9-24], [-51 15]) (mod 26) = ([9 2], [1 15]) .
Обновление: ознакомьтесь с Основами вычислительной теории чисел , чтобы узнать, как вычислить модульное обратное с расширенным алгоритмом Евклида. Обратите внимание, что -121 mod 26 = 9 , поэтому для gcd (9, 26) = 1 мы получаем (- 1, 3) .
-121 mod 26 = 9 , поэтому для gcd (9, 26) = 1 мы получаем (- 1, 3) . ознакомьтесь с Основами вычислительной теории чисел , чтобы узнать, как вычислять модульные обратные с помощью расширенного алгоритма Евклида. Обратите внимание, что -121 mod 26 = 9 , поэтому для gcd (9, 26) = 1 мы получаем (- 1, 3) .