Привет всем
Столкнулся на одном из параллельных форумов с очень интересным вопросом, связанным с кодированием информации.
Но речь сейчас не об этом. Дело вот в чем. Алгоритм кодирования подразумевает работу с матрицами по определенному модулю. В частности, при использовании только строчных латинских символов длина алфавита = 26, так что меня интересует именно работа по (mod 26). Вот пример:
допустим, матрица кодирования
|3 3|
T = | |
|2 5|
|3 3| |15| |45| |19|здесь - все логично... Непонятно дальше: для нахождения обратной T матрицы делаем так:
| | X | | = | | (mod 26) = | |
|2 5| | 0| |30| | 4|
|5 -3| |5 -3|
T^(-1) = (det T)^(-1) | | = (9)^(-1) | |
|-2 3| |-2 3|
(9)^(-1) (mod 26) ≡ 3
По определению, обратное число - такое, произведение которого с данным дает единицу, т.е. a^(-1) == b (mod c), если b * a == 1 (mod c).
В данном случае имеем: 3 * 9 == 27 == 1 (mod 26), поэтому 9 ^ (-1) == 3.
Угу... Это я нарыл. Теперь вопрос немного меняется:
Как однозначно по X и P определить X^(-1)? Есть какая-то общая формула?
X^(-1) mod P = (P+1) / X
работает иногда, но не всегда (в данном случае - да, в случае 15^(-1) mod 26 она работать не будет)...