Calculadora de exponenciación modular
Calcula a elevado a la potencia b, módulo m, incluso cuando los números tienen cientos de dígitos. La calculadora usa aritmética BigInt exacta y el método de elevar al cuadrado y multiplicar, y muestra cada paso con los dígitos binarios del exponente.
Última actualización:
Número entero, puede ser negativo. Funcionan expresiones como 2^64.
Número entero; si es negativo se usa el inverso modular
Número entero ≥ 1, p. ej. 1000000007 o 2^127-1
Cómo usar Calculadora de exponenciación modular
- Introduce la base a, p. ej. el valor de un mensaje en RSA.
- Introduce el exponente b; puede ser enorme, como 10^18.
- Introduce el módulo m, p. ej. 3233 o 10^9+7.
- Pulsa Calcular para obtener a^b mod m.
- Estudia la tabla para ver cada elevación al cuadrado y multiplicación.
Ejemplo resuelto: 3^13 mod 7 con cuadrado y multiplicación
13 en binario es 1101₂ (8 + 4 + 1). Eleva la base al cuadrado en cada paso y multiplica cuando el bit es 1, reduciendo mod 7 cada vez:
| Bit (de derecha a izquierda) | Potencia de la base mod 7 | Bit | Resultado acumulado |
|---|---|---|---|
| 0 | 3¹ ≡ 3 | 1 | 1 × 3 = 3 |
| 1 | 3² ≡ 9 ≡ 2 | 0 | 3 |
| 2 | 3⁴ ≡ 2² ≡ 4 | 1 | 3 × 4 = 12 ≡ 5 |
| 3 | 3⁸ ≡ 4² = 16 ≡ 2 | 1 | 5 × 2 = 10 ≡ 3 |
Así que 3^13 mod 7 = 3, obtenido con 3 elevaciones al cuadrado y 3 multiplicaciones. Comprobación con el pequeño teorema de Fermat: 7 es primo, así que 3^13 ≡ 3^(13 mod 6) = 3^1 = 3 ✓.
Reglas útiles
- Regla del producto: (x × y) mod m = ((x mod m) × (y mod m)) mod m, por eso es seguro reducir en cada paso.
- Fermat: si p es primo y p no divide a a, a^(p−1) ≡ 1 (mod p), así que b puede reducirse mod p − 1.
- Euler: de forma más general, si mcd(a, m) = 1 entonces a^φ(m) ≡ 1 (mod m), donde φ es la función phi de Euler.
- Costo: el método de cuadrado y multiplicación necesita como máximo 2·log₂(b) multiplicaciones modulares, así que incluso un exponente de 2048 bits requiere solo unos pocos miles de pasos.
- Los módulos habituales en concursos de programación son 10^9 + 7 y 998,244,353, ambos primos.
Preguntas frecuentes
¿Qué es la exponenciación modular?
Es calcular el resto de dividir a^b entre m, que se escribe a^b mod m. Por ejemplo 3^4 mod 5 = 81 mod 5 = 1. Es una operación fundamental en RSA, Diffie–Hellman, las pruebas de primalidad y el hashing.
¿Por qué no calcular simplemente a^b y luego tomar el resto?
a^b se vuelve astronómicamente grande: 2^(10^18) tiene unos 3 × 10^17 dígitos. Reducir mod m después de cada multiplicación mantiene todos los números por debajo de m², y la identidad (x·y) mod m = ((x mod m)(y mod m)) mod m garantiza el mismo resultado final.
¿Cómo funciona el método de cuadrado y multiplicación?
Escribe b en binario. Eleva repetidamente la base al cuadrado (a, a², a⁴, a⁸, … todo mod m) y multiplica en el resultado las potencias cuyo bit es 1. 3^13 usa 13 = 1101₂, así que 3^13 = 3^8 · 3^4 · 3^1. Esto requiere unos log₂(b) pasos en lugar de b − 1 multiplicaciones.
¿Cómo se usa en RSA?
El cifrado calcula c = m^e mod n y el descifrado calcula m = c^d mod n. Con la clave de libro de texto n = 3233, e = 17, d = 2753, el mensaje 65 se cifra como 65^17 mod 3233 = 2790, y 2790^2753 mod 3233 devuelve 65.
¿Qué significa un exponente negativo en aritmética modular?
a^(−k) mod m significa (a⁻¹)^k mod m, donde a⁻¹ es el inverso modular. Solo existe cuando mcd(a, m) = 1. Por ejemplo 7^(−1) mod 26 = 15, ya que 7 × 15 = 105 = 4 × 26 + 1.
¿Qué es el pequeño teorema de Fermat?
Si p es primo y a no es múltiplo de p, entonces a^(p − 1) ≡ 1 (mod p). Así que los exponentes pueden reducirse mod p − 1: 3^200 mod 13 = 3^(200 mod 12) mod 13 = 3^8 mod 13 = 9. La calculadora muestra este atajo siempre que el módulo es primo.
¿Se prueban todas las herramientas de FreeToolCabin para comprobar su calidad y precisión?
Sí. Cada herramienta del sitio pasa pruebas automáticas en navegadores reales para comprobar que el resultado es correcto y que no hay errores. Si encuentras un fallo o tienes una sugerencia, escríbenos a [email protected] y lo revisaremos.