Python Language Exponenciación modular: pow () con 3 argumentos.


Ejemplo

Al suministrar pow() con 3 argumentos pow(a, b, c) evalúa la exponenciación modular a b mod c :

pow(3, 4, 17)   # 13

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

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

Para los tipos incorporados, el uso de exponenciación modular solo es posible si:

  • El primer argumento es un int
  • El segundo argumento es un int >= 0
  • El tercer argumento es un int != 0

Estas restricciones también están presentes en Python 3.x

Por ejemplo, uno puede usar la forma de 3 argumentos de pow para definir una función inversa modular :

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]