Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Математика _ Работа с матрицами

Автор: volvo 1.10.2006 20:45

Привет всем smile.gif

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

Но речь сейчас не об этом. Дело вот в чем. Алгоритм кодирования подразумевает работу с матрицами по определенному модулю. В частности, при использовании только строчных латинских символов длина алфавита = 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


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

Автор: Michael_Rybak 2.10.2006 3:28

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

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

Автор: volvo 2.10.2006 3:36

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

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

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

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

Автор: Michael_Rybak 2.10.2006 14:03

Цитата(volvo @ 1.10.2006 23:36) *

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


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

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