Как работает оператор mod в схеме Эль-Гамаля?

Question

[Natalia64]

Пробую реализовать шифрование Эль-Гамаля https://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%B5%D...

Вроде бы mod - это остаток от деления. Но непонятно, как при расшифровке получается M.


Ведь 9 / 6^8 - число, близкое к 0. Тогда каким образом mod 11 этого числа равен 5?

Comments

[kalapanga]

Пятёрка посчитана по формуле которая там описана как "Для практических вычислений больше подходит следующая формула:" M = b*a^(p-1-x) mod p
По ней действительно получается: M = 9 * 6 ^ (11-1-8) mod 11 = 9 * 6 ^ 2 mod 11 = 9 * 36 mod 11 = 324 mod 11 = 5
Но объяснения, почему эти формулы заменяемы, я что-то тоже не понял.

[Lynn «Кофеман»]

Тут вам не поле действительных чисел и не может быть никаких «чисел близких к 0».

Степень -1 означает такое число которое при умножении на заданное даст в результате 1 по модулю p.

Например 2^-1 = 6.
Потому что 2 * 6 mod 11 = 12 mod 11 = 1.

[Lynn «Кофеман»]

https://ru.wikipedia.org/wiki/%D0%93%D1%80%D1%83%D...

[kalapanga]

Lynn «Кофеман», спасибо!

[Natalia64]

kalapanga, сделала вашим способом, спасибо!

Answer 1

[Ocelot]

В модульной арифметике a^-1 — это не 1/a, а обратное по модулю число, то есть такое, что a*a^-1 = 1 mod p

Comments

[Natalia64]

Решила в итоге методом:

Для практических вычислений больше подходит следующая формула:" M = b*a^(p-1-x) mod p

Но думаю Ваш ответ по сути правильный.