Что делает pow (a, b, c), когда показатель степени отрицателен?

Question

Python допускает третий аргумент во встроенной функции pow, который в основном вычисляет возведение в степень по модулю этого третьего аргумента (pow(a,b,c) = a**b % c).

Как это работает, когда показатель степени отрицателен? Например:

pow(6, -2, 13)
#-> 4

pow(6, -2, 12)
#-> Traceback (most recent call last):
#->  File "<stdin>", line 1, in <module>
#->  ValueError: base is not invertible for the given modulus

Answer 1

Из документации по встроенным функциям python:

Для операндов типа int и exp, если присутствует mod, mod также должен иметь целочисленный тип, а mod должен быть ненулевым. Если мод присутствует и exp отрицателен, база должна быть относительно простой к моду. В этом случае возвращается pow (inv_base, -exp, mod), где inv_base является обратным к основному модулю mod.

, что означает, что в вашем примере python вычисляет обратное значение 6 (так что 6 * inverse = 1) и рассчитывает pow(inverse, 2, 13). В этом случае обратное значение 6 мод 13 равно 11 (6 * 11 = 66 = 1 mod 13), и вы вычисляете 11 ** 2 = 121 = 4 mod 13.

Answer 2

pow(base, exp) =  base**exp
pow(12,2) = 144 = 12**2

Теперь вычисление модульных инверсий в поддерживаемых 3,8 впоследствии. До этого им было отказано в обратном базовому модулю

Answer 3

Вы пытались проверить это сами? Python раньше не поддерживал отрицательные показатели, когда был предоставлен третий аргумент, что они изменили в версии 3.8.x, и теперь он позволяет вычислять модульное обратное (в отличие от «стандартного» обратного при работе с реалов).

Итак, если пример pow (2, -1, 3) скажет вам обратное в моде 3, то будет 2, потому что 2 * 2 = 4 = 1 мод 3

Answer 4

Когда вторым аргументом является -1, он вычисляет модульную инверсию a (mod c). Использование других отрицательных степеней -n вернет модульное обратное к n -й степени (mod c).

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse