мультипликативный обратный?[закрыто]

Question

Я знаю, что аффинный шифр заменяет BD на SG.Мне нужно найти формулу шифрования в виде y = a x + b, где a и b — коэффициенты.Из приведенной выше информации мне в конечном итоге приходится использовать уравнения:a+b=18 и3a+b=6Итак, я работаю следующим образом:

a+b=18 and 3a + b = 6-> 3a+18-a=6->  2a= 6-18 -> 2a=14 (as it is mod 26)

b=18-a 

2a=? 

Итак, О хочу умножить на мультипликативную обратную величину 2 mod 26

Я не могу найти мультипликативное обратное число 2 с 26 (y = ax + b mod 26)

Кто-нибудь может помочь мне найти a и b?

Answer 1

Это потому, что 2 не имеет мультипликативного обратного мода 26:поскольку 13*2=0, не существует K такого, что K * a = 1.Ваш модуль должен быть простым.Попробуйте найти китайскую теорему об остатках для получения дополнительной информации.

Точнее, целые числа по модулю 26 не являются полем (математическим набором, в котором каждый элемент, кроме 0, имеет мультипликативную обратную величину).Любое кольцо, в котором a * b = 0 для некоторых a!=0 и b!=0, не является полем.

Фактически, поле всегда будет содержать p^n элементов, где p — простое число, а n — положительное целое число.Простейшие поля — это целые числа, модифицирующие простое число, но для степеней простых чисел необходимо построить более сложную систему.Короче говоря, используйте другой модуль, например 29.

Answer 2

А = 7 работает?2*7 = 14.Таким образом, b = 11.

Давайте проверим два уравнения, чтобы увидеть, работает ли это:

• 7+11 = 18 (проверьте первое уравнение).
• 3*7+11=21+11 = 32 = 6.

Что не так с вышеизложенным?

РЕДАКТИРОВАТЬ:Хорошо, теперь я понимаю, что может пойти не так, если попытаться выполнить деление на 2 по непростому модулю, поскольку это похоже на деление на 0.Вы можете воспользоваться предложением Рибонда об использовании китайской теоремы об остатках и разбить уравнения на другую пару пар:

мод 13:а+б=5, 3а+б=6.(2а = 1 = 14 => а=7.б=18-7=11.)

мод 2:а+б=0.3a+b=0 (Обратите внимание, что это одно и то же уравнение и имеет пару возможных решений, где a и b равны 0 или 1.)

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

Answer 3

Другие авторы правы в том, что не существует обратного числа 2 по модулю 26, поэтому вы не можете решить уравнение 2a=14 по модулю 26 путем умножения на обратное число 2.Но это не значит, что 2a=14 по модулю 26 неразрешима.

Рассмотрим общее уравнение cx = d mod n (в вашем случае c=2,d=14,n=26).Пусть g = НОД(c,n).Уравнение cx=d имеет решение, если an, только если g делит d.Если g делит d, то на самом деле существует несколько решений (из них g).Уравнение (c/g)x = d/g mod n/g имеет единственное решение (назовем его x_0), поскольку уравнение c/g относительно простое с n/g и, следовательно, имеет обратное.Решения исходного уравнения: x_0, x_0 + n/g, ..., x_0 + (g-1)n/g.

В вашем случае c=2,d=14,n=26 и g=2.g делит d, поэтому сначала решите уравнение (2/2)x = (14/2) mod (26/2), что дает 7.Итак, и 7, и 7+13=20 решают исходное уравнение.

Обратите внимание: это означает, что вы не определили однозначно свое аффинное преобразование, все еще существуют две возможности.Вам нужна еще одна точка данных...