Python Language Modular exponentiation: pow() with 3 arguments


Example

Supplying pow() with 3 arguments pow(a, b, c) evaluates the modular exponentiation ab mod c:

pow(3, 4, 17)   # 13

# equivalent unoptimized expression:
3 ** 4 % 17     # 13

# steps:
3 ** 4          # 81
81 % 17         # 13

For built-in types using modular exponentiation is only possible if:

  • First argument is an int
  • Second argument is an int >= 0
  • Third argument is an int != 0

These restrictions are also present in python 3.x

For example one can use the 3-argument form of pow to define a modular inverse function:

def modular_inverse(x, p):
    """Find a such as  a·x ≡ 1 (mod p), assuming p is prime."""
    return pow(x, p-2, p)

[modular_inverse(x, 13) for x in range(1,13)]
# Out: [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]