Exponenciación modular en Python

Dados tres números x, y y p, calcule (x^y) % p

Ejemplos:

Input:  x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.

Input:  x = 2, y = 5, p = 13
Output: 6
Explanation: 2^5 % 13 = 32 % 13 = 6.

El problema con las soluciones anteriores es que puede ocurrir un desbordamiento para un gran valor de n o x. Por lo tanto, la potencia generalmente se evalúa bajo módulo de un gran número.

La multiplicación ingenua es O(n) con un factor constante muy bajo con %m.
La función Pow calcula en tiempo O (log n) en python, pero toma mucho tiempo cuando los números son lo suficientemente grandes si primero calcula el valor de x y y luego lo modifica con p para obtener (x y ) % p evaluado.

# Simple python code that first calls pow() 
# then applies % operator.
a = 2
b = 100
p = (int)(1e9+7)
  
# pow function used with %
d = pow(a, b) % p
print (d)

Producción:

976371285

Al calcular con módulo de números grandes, el operador (%) toma mucho tiempo, por lo que se usa una Exponenciación Modular Rápida. Python tiene pow(x, e, m) para calcular el módulo, lo que lleva mucho menos tiempo. [Consulte Python Docs para obtener más detalles]

# Fast python code that first calls pow() 
# then applies % operator
a = 2
b = 100
p = (int)(1e9+7)
  
# Using direct fast method to compute 
# (a ^ b) % p.
d = pow(a, b, p)
print (d)

Producción:

976371285

El algoritmo de exponenciación modular rápida se ha explicado más brevemente en el enlace

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *