Работа с матрицами, по модулю (mod 26) Опции

[volvo]

Привет всем

Столкнулся на одном из параллельных форумов с очень интересным вопросом, связанным с кодированием информации.

Но речь сейчас не об этом. Дело вот в чем. Алгоритм кодирования подразумевает работу с матрицами по определенному модулю. В частности, при использовании только строчных латинских символов длина алфавита = 26, так что меня интересует именно работа по (mod 26). Вот пример:

допустим, матрица кодирования

    |3 3|
T = |   |
    |2 5|

умножаем ее на матрицу, представляющую 2 символа:

|3 3|   |15|    |45|            |19|
|   | X |  | =  |  | (mod 26) = |  |
|2 5|   | 0|    |30|            | 4|

здесь - все логично... Непонятно дальше: для нахождения обратной T матрицы делаем так:

                      |5 -3|            |5 -3|
T^(-1) = (det T)^(-1) |    | = (9)^(-1) |    |
                      |-2 3|            |-2 3|

Вот оно!!!
Документ, в котором описывается принцип кодирования, и дается несколько примеров, утверждает, что:

(9)^(-1) (mod 26) ≡ 3

Этого я не понял. Каким образом от 9 в минус первой степени по (mod 26) мы пришли к трем?

[Michael_Rybak]

По определению, обратное число - такое, произведение которого с данным дает единицу, т.е. a^(-1) == b (mod c), если b * a == 1 (mod c).

В данном случае имеем: 3 * 9 == 27 == 1 (mod 26), поэтому 9 ^ (-1) == 3.

[volvo]

Угу... Это я нарыл. Теперь вопрос немного меняется:

Как однозначно по X и P определить X^(-1)? Есть какая-то общая формула?

X^(-1) mod P = (P+1) / X

работает иногда, но не всегда (в данном случае - да, в случае 15^(-1) mod 26 она работать не будет)...

[Michael_Rybak]

Как однозначно по X и P определить X^(-1)? Есть какая-то общая формула?

Когда модуль простой, то обратное значение ищется с помощью малой теоремы Ферма - известно, что a^(p-1) == 1 (mod p), поэтому a^(-1) == a^(p-2), а в степень возводим за логарифм.

В случае составного модуля в ход вступает функция Эйлера, но тут уже без небольшого перебора, насколько я знаю, не обойтись. Хотя тут я плаваю.