Вопрос по теории вычетов

[Arc-en-Ciel]

Здравствуйте!
Если честно, очень не люблю задавать глупые вопросы, фактически с элементарным ответом, но, увы сама оказалась в таком положении, что не могу этого избежать.
Сейчас реализую метод Хилла, но вопрос не совсем по алгоритму, а по теории вычетов.
Мне для дешифрования необходимо найти обратную матрицу по модулю.
Если без усложнений, то:
выражение/det mod256 = x
все известно, нужно отсюда найти х.
но нельзя искать mod от дроби, от нецелого...
вроде можно расписать как:
х*det mod256 = выражение
Но, тем не менее, как выразить х-понятия не имею, не могу разобраться и найти подобный пример.
Не знаю, насколько по тематике сообщества, но помогите, пожалуйста разобраться в этом вопросе..
Заранее благодарю)

Comments

[[revolver]]

на самом деле нужно фактически реализовать поэлементное деление. но деление не просто, а "магическое", т.е. по модулю 256. Я уже точно не помню всю теорию, но примерно это выглядит так:

1. Вычеты по модулю это вообще говоря кольцо, а не поле, т.е. не всегда гарантируется существование обратного элемента для операции деления. Т.е. как минимум должно выполняться условия обратимости шифра.
2. Если мы гарантируем обратимость шифра, тогда всё переписывается так:

1/a * b = c --- все операции в поле по модулю m
эта запись равносильная такой: b = c*a mod m <=> c*a = q*m + b; получаем такое замечательное диафантово уравнение. Из которого моментально и следует вся мораль:
(мы не знаем c и не знаем q) перепишем немного вот так: a*C - m*Q = b. из условия разрешимости диофантовых уравнений в целых числах следует, что b mod (a, m) = 0, где запись (a, m) означает НОД.

Ну а для решения этого уравнения можно воспользоваться расширенным алгоритмом Евклида, который именно это и делает (Extended Euclidean algorithm). [смотреть теорию о диофантовых уравнениях]

Ну и всё. Дальше радуемся.

P.S. для нахождения обратной матрицы лучше воспользоваться LU разложением.

[Arc-en-Ciel]

Спасибо за объяснение...правда я все равно не очень понимаю эти преобразования, ну никак(
Сделала расширенный алгоритм евклида
ax+by=d
нашла d-НОД и коэффициенты x и у
как теперь привязать это к моему выражению? в чем связь? простите пожалуйста мою несообразительность(
выражение/det mod256 = XXX
если несложно, не могли бы еще раз объяснить, как мне найти этот ХХХ?

[[revolver]]

Arc-en-Ciel, чтобы это понять, нужно посмотреть на выражение

a mod b = c. чтоэто значит? Остаток от деления a на b = с. тоесть в a входит сколько-то целых кусков (q) нашего модуля (b), и остаток (c). Т.е. a mod b = c <=> a = q*b + c.
Теперь смотрим что у нас есть:
х*det mod256 = выражение. x*det mod 256 = v. <=> x*det = q*256 + v, где x, q - неизвестное. Переписываем это всё в виде:
x*det - q*256 = v --- похоже на диафантово уравнение?) Ну и так естественно для каждого элемента матрицы.