IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Работа с матрицами, по модулю (mod 26)
сообщение
Сообщение #1


Гость






Привет всем 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) мы пришли к трем?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

В данном случае имеем: 3 * 9 == 27 == 1 (mod 26), поэтому 9 ^ (-1) == 3.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






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

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

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

работает иногда, но не всегда (в данном случае - да, в случае 15^(-1) mod 26 она работать не будет)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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


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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 18:24
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name