Подскажите, как для линейного аффинного шифра вычислить а в минус первой степени? Если а - ключ, n - количество букв?
Есть какой-то другой метод, кроме метода подбора. Пример такой: 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 в минус первой. А дальше я не понимаю как это расписывается. Мне нужно именно подобным путем.
Есть другой пример:
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^(-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=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 в минус первой. А дальше я не понимаю как это расписывается. Мне нужно именно подобным путем.
Есть другой пример:
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