Как найти инверсию f (x) = (6x мод 13)? - PullRequest
Новая
       55

Как найти инверсию f (x) = (6x мод 13)?

0 голосов
/ 06 мая 2018

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

y = (6 * x) мод 13

x = (6 * y) мод 13

Ответы [ 2 ]

0 голосов
/ 06 мая 2018

Чтобы вычислить обратное значение y = 6 * x mod 13, я сначала собираюсь найти для x, а позже заменить x на y (и наоборот).

Поскольку y = 6 * x mod 13, x = 6^(-1) * y mod 13, где 6^(-1) - это модульный мультипликативный обратный из 6 для модуля 13. Теперь ваша задача - найти 6^(-1) mod 13. Другими словами, вы должны найти m такой, что 6 * m = 1 mod 13.

Обратите внимание, что 6 * 2 = 12 = -1 mod 13. Квадрат с обеих сторон 6 * 6 * 2 * 2 = 1 mod 13 или 6 * 24 = 1 mod 13. Поскольку 24 = 11 mod 13, следовательно 6 * 11 = 1 mod 13 и 11 = 6^(-1) mod 13.

Таким образом, наше уравнение для x теперь становится x = 11 * y mod 13. Заменив y -> x и x -> y, обратная функция задана как y = 11 * x mod 13.

Этот отличный Python-скрипт можно использовать для проверки правильности нашего результата: 

def f(x):
    return (6 * x) % 13

def f_inv(x):
    return (11 * x) % 13

for x in range(13):
    print x, f_inv(f(x)), x == f_inv(f(x))

При запуске выдает следующий вывод: 

0 0 True
1 1 True
2 2 True
3 3 True
4 4 True
5 5 True
6 6 True
7 7 True
8 8 True
9 9 True
10 10 True
11 11 True
12 12 True

Таким образом, подтверждая предпосылку, что f^(-1)(x) = 11 * x mod 13 удовлетворяет требуемой предпосылке, что f^(-1)(f(x)) = x.

0 голосов
/ 06 мая 2018

Инверсия этой функции будет определяться только для значений от 0 до 12. Также для каждого возможного y (от 0 до 12) будет бесконечное число возможных x, которые удовлетворяют уравнению.

Давайте попробуем решить для вас 

x = (6*y) mod 13
x + n*13 = (6*y)
y = (x + n*13)/6 | x ∈ {0,…,12}, n ∈ ℕ

где n - неизвестное положительное целое число, которое может иметь любое произвольное значение

...