Мультипликативная инверсия матрицы

@qmen · Регистрация: 13.10.2012

Студворк — интернет-сервис помощи студентам

Добрый день,я изучаю сейчас матрицы и вот в чём вопрос как найти мультипликативную инверсию матрицы?Желательно просто и понятно,в гугле искал не помогло.Заранее благодарю за ответ

@palva · 20.01.2014, 00:55

Может так умно называется взятие обратной матрицы?

@Ваю · 04.03.2020, 22:01

Аддитивная инверсия матрицы [a + b ≡ 0 (mod n)] — это другая матрица В, такая, что А + В = 0. Другими словами, мы имеем элементы b_tj = —a_ij для всех значений i и j. Обычно аддитивная инверсия А обозначается как (-А).

Мультипликативная инверсия матрицы [a × b ≡ 1 (mod n)] определена только для квадратных матриц. Мультипликативная инверсия квадратной матрицы А — квадратная матрица В, такая, что АхВ = ВхА = 1. Обычно мультипликативная инверсия обозначается как А^(-1). Мультипликативная инверсия существует только, если det(А) имеет мультипликативную инверсию в соответствующем инверсном множестве. Если целое число не имеет мультипликативной инверсии в Z, то не существует мультипликативной инверсии матрицы в Z. Однако матрицы с реальными элементами имеют инверсии, только если det(А) != 0.

Это применяется в криптографии.

Шифр Хилла

Для расшифровки нужно найти мультипликативную инверсию матрицы. C = P x K => K = C x P^(-1)
K^(-1) не является обратной матрицей для K.
Имеющиеся примеры:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
а) Шифрование
     C             P             K
14 07 10 13   02 14 03 04   09 07 11 13
08 07 06 11 = 08 18 17 04 X 04 07 05 06
11 08 18 18   00 03 24 25   02 21 14 09
                            03 23 21 08
 
б) Дешифрование
     P             C          K^(-1)
02 14 03 04   14 07 10 13   02 15 22 03
08 18 17 04 = 08 07 06 11 X 15 00 19 03
00 03 24 25   11 08 18 18   09 09 03 11
                            17 00 04 07
 
в) Взлом
   P            C
05 07 10     03 06 00
13 17 07 <-> 14 16 09
00 05 04     03 17 11
 
   K        P^(-1)       C
02 03 07   21 14 01   03 06 00
05 07 09 = 00 08 25 X 14 16 09
01 02 11   13 03 08   03 17 11

Кто-то может объяснить как находится всё это? Даже с мультипликативной инверсией числа ничё не понятно.
В инете по большому счёту пишут, только что 3 × 7 ≡ 1 (mod 10), но как это найдено?

@palva · 04.03.2020, 22:49

Сообщение от Ваю

C = P x K => K = C x P^(-1)

Почему? Сначала объясните, как вы это получили.

Байт · 04.03.2020, 22:54

palva, имхо, там те же яйца, только над полем mod(n) (Если n - простое) Если n - не простое, тогда - над кольцом. Что интереснее. Однако, сумбурности изложения уважаемым Ваю своей проблемы это не отменяет.

@palva · 04.03.2020, 23:04

Сообщение от Байт

только над полем mod(n) (Если n - простое)

Это как раз понятно. Мой вопрос связан с тем, что я полагал правильным C = P x K => P = C x K^(-1) Но пусть Ваю приведет свои резоны. И почему он сразу пишет, что

Сообщение от Ваю

K^(-1) не является обратной матрицей для K.

тогда как только что ввел обозначения, по которым является.

@Ваю · 04.03.2020, 23:36

Я переписал то, что есть в книге, никаких пояснений там нет, только это и всё...

Добавлено через 2 минуты

Сообщение от palva

Но пусть Ваю приведет свои резоны. И почему он сразу пишет, что...

Перемножте матрицы К и К^(-1), единичной там ни разу не получается, я проверял в экселе, сначала подумал, что это всё же обратная, просто помноженная на определитель, но ничё подобного.

Хотя бы с обычными числами разобраться и уже было бы замечательно, про разбор получения матрицы особо даже не мечтаю. Так же сказано, что эта мультипликативная инверсия является или связана с раширенным НОД, но мне это тоже мало что даёт, я не понял как с её помощью расшифровать текст. Да и алгоритм получения чисел s и t тоже не ясен.

@palva · 04.03.2020, 23:43

Ну если вы этот текст переписали бездумно и, возможно, с ошибками, и защищать его правильность не беретесь, тогда в чем ваш вопрос?

Добавлено через 3 минуты
Вы думаете, что в матрице целые числа? Может быть вычеты по простому модулю? Эксель же работал с ними как с целыми числами. Естественно, единичной матрицы не получилось.

@Ваю · 04.03.2020, 23:57

Вопрос в том как составить допустимую матрицу и как найти инверсию. Я ещё раз повторю, что это копипаста из книги символ в символ, кроме этого там нет ничего, что и как я могу узнать и разобраться исходя из этого? Я задаю вопросы исходя из того, что у меня есть, а у меня ничего нет.

@palva · 05.03.2020, 00:52

Допустимая матрица -- я не знаю, что это такое. Нигде в ветке этот термин не применялся.
Найти обратную можно по тому же алгоритму, что и для обычной матрицы над полем. Только в вашем случае непонятно, что у вас за поле. Скорее всего, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\mathbb Z}/p{\mathbb Z}.$ Только непонятно, чему равно простое $https://www.cyberforum.ru/cgi-bin/latex.cgi?p.$

Добавлено через 27 минут
Ну вот смотрите. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?p=7.$ Матрица второго порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}3&2\\5&4\end{pmatrix}.$ Ищем к ней обратную...

Добавлено через 7 минут
Определитель равен 2. Обратная величина 4. Умножаем 4 на транспонированную матрицу алгебраических дополнений.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?4\cdot \begin{pmatrix}4&-2\\-5&3\end{pmatrix}=4\begin{pmatrix}4&5\\2&3\end{pmatrix}=\begin{pmatrix}16&20\\8&12\end{pmatrix}=\begin{pmatrix}2&6\\1&5\end{pmatrix}.$
Для проверки можете перемножить в вашем любимом экселе, а потом возьмите остатки при делении на 7.

Вот здесь обратная матрица вычисляется онлайн https://planetcalc.ru/3324/

Добавлено через 7 минут

Сообщение от Ваю

Да и алгоритм получения чисел s и t тоже не ясен.

Мы даже не знаем, что такое эти числа. Первый раз про них слышим в этой ветке. А уж помочь вам в их получении -- извините...

@Ваю · 05.03.2020, 15:05

Сообщение от palva

Допустимая матрица -- я не знаю, что это такое.

Это та, для которой есть обратная, для обычной матрицы определитель не должен быть равен нулю, а что тут нужно я не знаю, наверно тоже самое, но это не точно.

Сообщение от palva

что и для обычной матрицы над полем

Что вообще за поле такое? Я в матрицах знаю только определитель, ранг и собственные значения, из преобразований - как получить треугольную, тридиагональную и обратную матрицы, ну и само собой перемножать умею, а так же находить решение системы линейных уравнений.

Сообщение от palva

Обратная величина 4.

К чему или от чего она обратная и как найдена?

Сообщение от palva

4 -2
-5 3

Данная обратная матрица помножена на определитель и потом ещё на это обратное число во всех ячейках, это ни на что не влияет? И эксель не мой любимый.

Сообщение от palva

Мы даже не знаем, что такое эти числа.

Это стандартные обозначения чисел раширенного НОДа, как я писал выше, они якобы нужны для расшифровки кода, полученного при перемножении исходного кода на ключ и нахождения остатка от деления на длину алфавита после этого. При этой операции целая часть числа теряется, поэтому информация становится неполной и получить исходное сообщение напрямую нельзя, разве что поиском по построенной заранее таблице переобразований.

Ряд 0, 1, 2, 3, ..., 32 при шифровании c ключом 7 и алфавитом в 33 символа преобразуется в ряд

0, 7, 14, 21, 28, 2, 9, 16, 23, 30, 4, 11, 18, 25, 32, 6, 13, 20, 27, 1, 8, 15, 22, 29, 3, 10, 17, 24, 31, 5, 12, 19, 26

согласно формуле [у = (7х) мод 33], вот, а для обратного преобразования якобы нужно к чему-то от чего-то как-то находить мультипликативную инверсию. Меня можете не спрашивать - в книге вообще ничего вменяемого по данному поводу нет, просто ставят перед фактом и всё. Про существование модульной математики я понял, но больше о ней я ничего не знаю и тем более не умею решать модульные уравнения. Да, вы наверно правильно догадались - в примерах решений этих уравнений есть только условие и ответ, но не само решение, догадайтесь сами как их делать.

@palva · 05.03.2020, 17:59

Сообщение от Ваю

для обычной матрицы определитель не должен быть равен нулю

И здесь тоже. Только здесь числом нуль называется любое число, при делении которого на 7 (в моем случае) получается остаток нуль. То есть в матрице стоят не числа, а их остатки от деления на 7, и при арифметических операциях в качестве результата можно принимать остаток от деления результата на 7. Поскольку все числа, которые при делении на 7 дают один и тот же остаток мы считаем одним и тем же числом. Но это в моем случае. Какие элементы матриц используете вы, это надо у вас спрашивать. В криптографии обычно p= какому-то большому простому числу. А может быть и не простому, но для таких p я обратную матрицу находить не берусь. Не изучал такой теории.

Сообщение от Ваю

Я в матрицах знаю только определитель, и т. д.

Всю теорию, которую вы уже знаете, вы можете применять и здесь. Только действия над числами будут немного другими. Каждый раз берем остаток от деления на p. Ну и p должно быть простым, тогда эти "числа" гарантированно можно делить, если не на нуль.

Сообщение от Ваю

К чему или от чего она обратная и как найдена?

К числу 2, естественно. 2 умножить на обратный к 2 должно получиться 1. Ну вот 2*4 = 8. Остаток от деления на 7 один. Значит, пишем =1. Как нашел? подбором. Когда возможных остатков всего 7 их недолго перебрать. А вообще применяют расширенный алгоритм евклида, находят те самые r и s, о которых вы упоминали.

Сообщение от Ваю

Данная обратная матрица помножена на определитель...

Это не обратная матрица. В этой строке я нахожу обратную матрицу. Обратная матрица в конце строки. Проверяем:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}3&2\\5&4\end{pmatrix}\begin{pmatrix}2&6\\1&5\end{pmatrix}=\begin{pmatrix}8&28\\14&50\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$
Получили единичную матрицу. То есть это и в самом деле обратная матрица.

Сообщение от Ваю

согласно формуле [у = (7х) мод 33],

Вот вы и проговорились, Штирлиц. Оказывается у вас p=33. Это то, чего мы от вас и добивались. Но у вас p составное. То есть матрица будет не над полем, а над кольцом, а вместо линейного пространства будет модуль. Наверно, работает тот же алгоритм. Попробуйте на примере 2x2-матрицы. Вместо 7 будет 33. В этом случае алгоритм не будет работать, если определитель равен 0, 3 или 11, поскольку в этом случае вы не сможете взять обратное значение от определителя.

Добавлено через 15 минут
Тот сайт, на который я ссылался, дает при p=33 к матрице $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}4&18\\26&5\end{pmatrix}$ обратную $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}31&27\\17&5\end{pmatrix}.$ Там ниже алгоритм тоже приводится. Он тот же, что и я выше использовал.

@Ваю · 05.03.2020, 21:18

Сообщение от palva

Это не обратная матрица.

Обратная, помноженная на определитель для той, что выше, а дальше она преобразуется чтоб были остатки. Тут я не доконца понял, где именно не должно быть кратных значений, в определителе, ячейках матрицы или ещё где?

Сообщение от palva

Получили единичную матрицу. То есть это и в самом деле обратная матрица.

Единичная матрица получается при нахождении остатков от деления. Понятно.

Сообщение от palva

Оказывается у вас p=33.

Это пример для русского алфавита и у меня ничего нет, я разбираюсь в теории, а не решаю задачу, до решений ещё далеко и это обозначается как Z_n, а не p. На счёт него есть задачи, где надо найти подмножество, делать подобное перебором просто тупо, на сколько я понял есть какой-то способ находить решение с помощью расчётов с использованием расширенного НОДа.

Сообщение от palva

4 18
26 5

определитель = -448 => -448 мод 33 = -19, значит к 33-19=14 надо искать инверсию, её ищат не переборм, но как я не знаю, там написано про расширенный НОД, про который я уже много раз спросил. На калькуляторе выдаёт 26, получается

Code
1
2
26 x 5 -18 = 130 -468 => mod 33 => 31 27
     -26 4   -676 104              17 5

При делении находятся положительные остатки, тут вроде как понятно.

Байт · 05.03.2020, 22:03

Сообщение от Ваю

Что вообще за поле такое?

Ну, если ТС плохо себе представляет, что такое поле (в алгебраическом смысле), что такое матрица над полем, и его смущают обозначения и понятия типа Z/Zp, и ему трудно понять, что это тоже самое, что арифметика по модулю p, то разговор тяжелый получается.
Эти основы Алгебры надо все-таки знать, прежде чем браться за подобные задачи. И эти основы не так уж и сложны, не надо быть Эйлером или Перельманом, чтоб понять о чем речь идет. Но усвоив их, вы сможете более адекватно общаться с людьми, которым удалось узнать и понять.
Повторяю. В этих понятиях не ничего страшного, нет ничего недоступного обычному человеческому уму. И, может быть, стоит потратить несколько дней на их освоение. Тогда и вы более внятно изложите свою задачу, и нам будет легче вам помочь. И многие (не скажу, что все) ваши проблемы будут вам более понятны.

@palva · 05.03.2020, 23:51

Не по теме:

Сообщение от Байт

И эти основы не так уж и сложны

Лично я познал это между 9 и 10 классом в месячной летней школе. Прохождение летней школы и сдача экзаменов было формой приема в 10 класс математической школы-интерната № 18. За месяц мы прошли производные, интегралы, нахождение площадей, углов (между кривыми), композиция отображений, комплексные числа и кватернионы, определение группы, кольца, поля, тела, нормальной подгруппы, фактор-группы, т. Лагранжа, кольца вычетов, т. Ферма, функция Эйлера, т. Эйлера. Линейной алгебры не касались. На экзаменах спрашивали доказательства и давали задачи. Каждый день три пары занятий, потом всякий спорт и классическая музыка. Жили в палатках, плавали на лодках вместе с акад. Колмогоровым по Можайскому водохранилищу. Один раз приезжал П. С. Александров, но с нами он не общался, только привез пластинки и жену Колмогорова. А Колмогоров немного читал нам разный непонятный и необязательный дополнительный материал, принимал экзамены. Немного дополнительной физики было - уравнение Ван-дер-Ваальса. Но по физике экзамена не было. Только алгебра и анализ. Десятый класс был выпускным. Тогда учились 10 лет.

Я это к тому, что нескольких дней на это не хватит. Прочитать и понять можно. Но чтоб возникла интуиция нужно прорешать много задач и хотя бы неделю над этим помедитировать.

@Ваю · 05.03.2020, 23:59

Я не на математическом учился, у нас даже такого факультета нет, а на том, что есть учат немного только самого обычного и простого. Что касается интегралов с производными и пределами - я их забыл 20 лет тому назад.

Добавлено через 7 минут
А по поводу матриц, то для нахождения определителя матрицы, треугольной матрицы и обратной матрицы - я для этого использую модификацию Барейса, алгоритм нахождения обратной матрицы этим способом я восстановил сам, в интернетах его нет, он намного тупее стандартных способов и несколько более быстрый. Хотя да, некоторый недостаток у него есть, который одновременно является достоинством, смотря какой размер матрицы и диапазон значений.

@palva · 06.03.2020, 00:03

Ну если взять учебник криптографии, то там бывает хорошее введение в начала теории чисел и алгебры. Например, у меня на полке стоит. Ю. С. Харин и др. Математические и компьютерные основы криптологии. Минск, 2003. Рекомендую прочитать вторую и третью главы. Всё нужное и ничего лишнего.

Добавлено через 1 минуту

Сообщение от Ваю

я для этого использую модификацию Барейса

не слышал про него. По жизни не сталкивался.

@Ваю · 06.03.2020, 00:14

Сообщение от palva

не слышал про него. По жизни не сталкивался.

Его не учат в институтах чтоб студенты не раслаблялись, он на двух пальцах одной руки объясняется и делает половину всего, что можно перечислить с матрицами, изучаемого на первом курсе точно. Обратную матрицу для тридиагональной мне было лень расписывать, поэтому только 3х3. Расчитываемые ячейки обозначены жёлтым, всё остальное всеми цветами - переписывание значений ячеек "как есть" без вычислений, а жёлтого там очень мало. Короче в файле расписаны матрицы от 2х2 до 5х5 на разных страницах.

@kabenyuk · 06.03.2020, 14:20

Сообщение от Ваю

в интернетах его нет

Почему же нет? Очень даже есть - вот не самая содержательная, но как отправная точка

@palva · 08.03.2020, 10:07

Когда-то я пытался использовать метод https://pdfs.semanticscholar.o... 3fcc77.pdf
Ссылка на эту статью есть в книге Ланса https://urss.ru/cgi-bin/db.pl?... k&id=31053 Там метод статьи изложен, но неправильно. Я был очень возмущен и решил свои проблемы другими способами. Уже ближе к современности, когда появился интернет, я устроил раскопки и нашел оригинал статьи. Но изучить ее руки не дошли.

Новые блоги и статьи Все статьи Все блоги /
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Вот уже год прошел, как у меня домен в reg.ru ... Etyuhibosecyu 16.04.2026 И ничего они мне не сделали. Если отвязать карту, никакие услуги они не навяжут. Я бы с радостью продлил еще на два года, чтобы не мучиться с временным доменом и меня уже знали по red-star-soft. com,. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@qmen 9 / 9 / 2 Регистрация: 13.10.2012 Сообщений: 36

	Мультипликативная инверсия матрицы 19.01.2014, 21:35. Показов 5521. Ответов 19 Метки нет (Все метки) Добрый день,я изучаю сейчас матрицы и вот в чём вопрос как найти мультипликативную инверсию матрицы?Желательно просто и понятно,в гугле искал не помогло.Заранее благодарю за ответ 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	20.01.2014, 00:55
	Может так умно называется взятие обратной матрицы? 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	04.03.2020, 22:54
	palva, имхо, там те же яйца, только над полем mod(n) (Если n - простое) Если n - не простое, тогда - над кольцом. Что интереснее. Однако, сумбурности изложения уважаемым Ваю своей проблемы это не отменяет. 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	04.03.2020, 23:43
	Ну если вы этот текст переписали бездумно и, возможно, с ошибками, и защищать его правильность не беретесь, тогда в чем ваш вопрос? Добавлено через 3 минуты Вы думаете, что в матрице целые числа? Может быть вычеты по простому модулю? Эксель же работал с ними как с целыми числами. Естественно, единичной матрицы не получилось. 0

@Ваю 27 / 27 / 9 Регистрация: 21.04.2015 Сообщений: 704
	04.03.2020, 23:57
	Вопрос в том как составить допустимую матрицу и как найти инверсию. Я ещё раз повторю, что это копипаста из книги символ в символ, кроме этого там нет ничего, что и как я могу узнать и разобраться исходя из этого? Я задаю вопросы исходя из того, что у меня есть, а у меня ничего нет. 0

@Ваю 27 / 27 / 9 Регистрация: 21.04.2015 Сообщений: 704
	05.03.2020, 23:59
	Я не на математическом учился, у нас даже такого факультета нет, а на том, что есть учат немного только самого обычного и простого. Что касается интегралов с производными и пределами - я их забыл 20 лет тому назад. Добавлено через 7 минут А по поводу матриц, то для нахождения определителя матрицы, треугольной матрицы и обратной матрицы - я для этого использую модификацию Барейса, алгоритм нахождения обратной матрицы этим способом я восстановил сам, в интернетах его нет, он намного тупее стандартных способов и несколько более быстрый. Хотя да, некоторый недостаток у него есть, который одновременно является достоинством, смотря какой размер матрицы и диапазон значений. 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	08.03.2020, 10:07
	Когда-то я пытался использовать метод https://pdfs.semanticscholar.o... 3fcc77.pdf Ссылка на эту статью есть в книге Ланса https://urss.ru/cgi-bin/db.pl?... k&id=31053 Там метод статьи изложен, но неправильно. Я был очень возмущен и решил свои проблемы другими способами. Уже ближе к современности, когда появился интернет, я устроил раскопки и нашел оригинал статьи. Но изучить ее руки не дошли. 0