pythonpow

Python pow() and modulus


The pow() function in Python3 provide the values for exponents.

>>>pow(2, 3)
8

Python3 has support to negative exponents that is can be represented using pow(10, -1). When I calculated pow(4, -1, 5), it gave the output 4.

>>> pow(4, -1, 5)
4

I couldn't understand how the value 4 was calculated because, in the background, it performs and it didn't return a value 4 as a reminder when I calculated manually.

When -ve value is passed in two values it responds with the desired output as a manual method.

>>> pow(4, -1)
.25

What is the difference when calculating a negative exponent with a modulus?


Solution

  • Starting in python 3.8, the pow function allows you to calculate a modular inverse. As other answers have mentioned, this occurs when you use integers, have a negative exp, and base is relatively prime to mod. (this is the case in your example)

    What is a modular inverse?

    Lets start with normal inverses. Some number Y has an inverse X such that Y * X == 1. Modular inverses are very similar. For some number Y and some modulus mod, there exists an inverse X such that ((X * Y) % mod) == 1. From your example, you will see (4 * 4) % 5 does in fact equal 1, making 4 a valid modular inverse for Y = 4 and mod = 5.

    How do you just get pow(4, -1, 5) == 0.25

    Well, you could write it as separate steps (4 ** -1) % 5, but as the documentation says

    if mod is present, return base to the power exp, modulo mod (computed more efficiently than pow(base, exp) % mod)

    So you may sacrifice performance by using (4 ** -1) % 5. Unfortunately, it does not seem possible to do with pow.