Деление в модульной арифметике

Question

Если X = (a * b) mod (c), и мы знаем значение «b» и «c», но не «a», как мы можем найти (a) mod (c)?

Можем ли мы сделать это как X, разделенное на (b) mod (c) или что-то в этом роде?

Answer 1

Ваше предложение не работает.

Например

(3 * 4 ) mod 7 = 5
but 3 mod 5 != 5 / (4 mod 7) = 5/4

В этом случае мы могли бы отметить, что

(4*2 ) mod 7 = 1

, а затем

(2 * ((3 * 4) mod 7) mod 7
= 24 mod 7 = 3 = 3 mod 7

и вообще, если b и c не имеют общих делителей, тогда есть ab 'с

(b'*b ) mod c = 1

, а затем

(b' * ((a*b) mod c) ) mod c
= (a* ((b'*b) mod c)) mod c
= (a*1) mod c
= a mod c

Учитывая b и c без общих делителей вы можете найти b ', как указано выше, с помощью расширенного алгоритма Евклида