➗

Calculadora de exponenciación modular — aᵇ mod m (potencia modular)

Calcula aᵇ mod m con exponentes enormes mediante el método de elevar al cuadrado y multiplicar: el resultado, b en binario, cada paso en una tabla y el número de multiplicaciones.

Base a

Exponente b

Módulo m

Cargando calculadora…

Cómo funciona

Escribe b en binario, b = Σ bᵢ·2ⁱ · aᵇ = ∏ (a^(2^i))^(bᵢ) · eleva al cuadrado repetidamente: a^(2^(i+1)) = (a^(2^i))² mod m · multiplica el resultado por a^(2^i) mod m cada vez que el bit bᵢ = 1 · reduce mod m en cada paso

Elevar un número a una potencia enorme y luego reducir necesitaría valores intermedios gigantescos. La exponenciación modular lo evita reduciendo después de cada multiplicación, lo cual es válido porque (x·y) mod m = ((x mod m)(y mod m)) mod m. El método binario de derecha a izquierda eleva la base al cuadrado una vez por cada bit del exponente y la multiplica en el resultado por cada bit 1, así que solo hacen falta unos log₂ b pasos. Es la operación central de RSA, Diffie–Hellman y las pruebas de primalidad (Knuth, The Art of Computer Programming, vol. 2, §4.6.3). Toda la aritmética usa enteros grandes exactos.

Ejemplo resuelto

4¹³ mod 497: 13 = 1101 en binario. Cuadrados módulo 497: 4, 16, 256, 256² = 65,536 mod 497 = 429. Multiplica los de los bits 0, 2 y 3: 4 × 256 = 1,024 mod 497 = 30, y 30 × 429 = 12,870 mod 497 = 445. Así, 4¹³ mod 497 = 445 (comprobación: 4¹³ = 67,108,864 = 135,027 × 497 + 445).

Fuentes: Wolfram MathWorld — Modular Exponentiation (Power) · Wikipedia — Modular exponentiation (right-to-left binary method)

Preguntas frecuentes

¿Cómo se calcula a mano una potencia grande módulo n?

Escribe el exponente en binario, arma la tabla a, a², a⁴, a⁸, … reduciendo módulo n cada vez, multiplica las entradas que corresponden a los bits 1 y vuelve a reducir.

¿Por qué no calcular aᵇ primero y luego sacar el residuo?

Con exponentes de cientos o miles, aᵇ tiene más cifras de las que cualquier calculadora puede manejar. Reducir en cada paso mantiene todos los números por debajo de m².

¿El teorema de Fermat o el de Euler lo hacen más rápido?

Sí. Si mcd(a, m) = 1 puedes reducir antes el exponente módulo φ(m), ya que a^φ(m) ≡ 1 (mod m). Para un módulo primo p, φ(p) = p − 1.

¿Cuánto vale 0⁰ mod m aquí?

La calculadora sigue la convención usual 0⁰ = 1, así que 0⁰ mod m = 1 (o 0 cuando m = 1).

Calculadoras relacionadas

Calculadora de la función phi de Euler

Calcula la función phi de Euler φ(n), la cantidad de enteros del 1 al n que son coprimos con n, con la factorización en primos y la fórmula del producto, y la lista de coprimos para n pequeños.

Calculadora de inverso modular

Calcula el inverso multiplicativo modular de a módulo m con el algoritmo de Euclides extendido: cada división, la identidad de Bézout, la comprobación y cuándo no existe inverso.

Calculadora de módulo y residuo

Calcula el residuo (a mod b) y el cociente de una división, con el módulo truncado y el módulo redondeado hacia abajo para números negativos. Resultado al instante.

Calculadora de congruencias lineales

Resuelve la congruencia lineal ax ≡ b (mod m): comprueba si mcd(a, m) divide a b, reduce la congruencia, halla el inverso modular y lista todas las soluciones módulo m.

Esta calculadora tiene fines informativos. Verifica los resultados importantes antes de tomar decisiones.