Ответы Mail
Программирование
Android
C/C++
C#
iOS
Java
JavaScript
jQuery
SQL
Perl
PHP
Python
Веб-дизайн
Верстка, CSS, HTML, SVG
Системное администрирование
Другие языки и технологии
Лидеры категории
Лена-пена
М.И.
Y.Nine
•••
Искусственный Интеллект
Искусственный Интеллект
Искусственный Интеллект
Подскажите, как для линейного аффинного шифра вычислить а в минус первой степени? Если а - ключ, n - количество букв?
Ирина Богатырева
(169),
на голосовании
8 лет назад
Дополнен 8 лет назад
Есть какой-то другой метод, кроме метода подбора. Пример такой: a=8, n=35. Там еще НОД нужно расписывать... Вроде так: НОД (35,8) 35=8*4+3 НОД (8,3) 8=3*2+2 НОД (3,2) 3=2*1+1. Потом u,v - (u*8+v*35=1)mod211 (u*8)mod35+ (v*35)mod35=1 (u*8)mod35=1 u=a в минус первой. А дальше я не понимаю как это расписывается. Мне нужно именно подобным путем.
Дополнен 8 лет назад
Есть другой пример:
a=7,n=37
НОД (37,7) 37=7*5+2
НОД (7,2) 7=2*3+1
u,v - (u*7+v*37=1)mod37
(u*7)mod37+ (v*37)mod37=1
(u*7)mod37=1
u=a в минус первой степени
1=7-3*2=7-3*(37-5*7)=16*7-3*37=1
a=7,n=37
НОД (37,7) 37=7*5+2
НОД (7,2) 7=2*3+1
u,v - (u*7+v*37=1)mod37
(u*7)mod37+ (v*37)mod37=1
(u*7)mod37=1
u=a в минус первой степени
1=7-3*2=7-3*(37-5*7)=16*7-3*37=1
Голосование за лучший ответ
Шумахер
(8066)
8 лет назад
a^(-1) это число, которое удовлетворяет уравнению
a * [ a^(-1) ] mod n = 1
Дальше писать?
Если a^(-1) принять за "x", то
(a * x) mod m = 1
a * x = m + 1
x = (m + 1) / a
Пример из вики если брать, то там не объясняют как получено a^(-1), но в нем a = 3 и m = 26, а в примере для дешифровки a^(-1) = 9
Проверим?
x = (26 + 1) / 3 = 9.
a * [ a^(-1) ] mod n = 1
Дальше писать?
Если a^(-1) принять за "x", то
(a * x) mod m = 1
a * x = m + 1
x = (m + 1) / a
Пример из вики если брать, то там не объясняют как получено a^(-1), но в нем a = 3 и m = 26, а в примере для дешифровки a^(-1) = 9
Проверим?
x = (26 + 1) / 3 = 9.
Ирина БогатыреваУченик (169)
8 лет назад
Есть какой-то другой метод, кроме метода подбора. Пример такой: a=8, n=35. Там еще НОД нужно расписывать... Вроде так: НОД (35,8) 35=8*4+3 НОД (8,3) 8=3*2+2 НОД (3,2) 3=2*1+1. Потом u,v - (u*8+v*35=1)mod211 (u*8)mod35+ (v*35)mod35=1 (u*8)mod35=1 u=a в минус первой. А дальше я не понимаю как это расписывается. Мне нужно именно подобным путем.
Шумахер
Мыслитель
(8066)
Ну логично, что правильнее будет написать все таки
x = (k*m + 1) / a
k - целое и такое, что x - целое.
Число х - еще называют мультипликативной инверсией
http://e-maxx.ru/algo/reverse_element
Да, по сути ее поиск - это некий подбор. Но любой подбор можно окружить терминами и правилами и получить алгоритм.
Ирина БогатыреваУченик (169)
8 лет назад
Есть другой пример:
a=7,n=37
НОД (37,7) 37=7*5+2
НОД (7,2) 7=2*3+1
u,v - (u*7+v*37=1)mod37
(u*7)mod37+ (v*37)mod37=1
(u*7)mod37=1
u=a в минус первой степени
1=7-3*2=7-3*(37-5*7)=16*7-3*37=1
a=7,n=37
НОД (37,7) 37=7*5+2
НОД (7,2) 7=2*3+1
u,v - (u*7+v*37=1)mod37
(u*7)mod37+ (v*37)mod37=1
(u*7)mod37=1
u=a в минус первой степени
1=7-3*2=7-3*(37-5*7)=16*7-3*37=1
Шумахер
Мыслитель
(8066)
Ну по идее
7 * 16 mod 37 = 1
16 = (3*37+1)/7
Похожие вопросы