Calculadora de Exponenciación Modular

Calculadora de Exponenciación Modular

La Calculadora de Exponenciación Modular calcula \(a^b \bmod n\) — elevando una base \(a\) a un exponente \(b\) y tomando el resto al dividir por el módulo \(n\). Utiliza el algoritmo de exponenciación binaria (también llamado potencia rápida o exponenciación por cuadrados), que reduce la operación de \(O(b)\) multiplicaciones a solo \(O(\log b)\). Este es el mismo algoritmo utilizado en implementaciones criptográficas del mundo real como RSA, Diffie-Hellman y ElGamal.

Aplicaciones de la exponenciación modular

Cómo funciona el algoritmo de exponenciación binaria

La idea clave es que podemos descomponer cualquier exponente en una suma de potencias de 2 usando su representación binaria. Por ejemplo, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), por lo tanto \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

El algoritmo procesa los dígitos binarios del exponente de izquierda a derecha:

Pseudocódigo

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // el bit es 1
            result = (result × base) mod mod
        exp = exp >> 1        // desplazamiento a la derecha (dividir por 2)
        base = (base × base) mod mod
    return result

Fórmulas clave

Cómo usar la Calculadora de Exponenciación Modular

1. Ingrese la base (a): Este es el número que desea elevar a una potencia. Puede ser positivo o negativo. Por ejemplo, ingrese 7 para calcular 7^256 mod 13.
2. Ingrese el exponente (b): Debe ser un número entero no negativo. Representa la potencia. Para aplicaciones criptográficas, esto puede ser muy grande (la calculadora admite hasta 10^18).
3. Ingrese el módulo (n): Debe ser un número entero positivo. Es el número por el cual divide para obtener el resto. En RSA, esto suele ser el producto de dos números primos grandes.
4. Haga clic en Calcular: La calculadora computa a^b mod n usando exponenciación binaria y muestra el resultado al instante.
5. Vea la animación: Presione Reproducir para ver el algoritmo de exponenciación binaria ejecutarse paso a paso. Cada bit del exponente se procesa en secuencia, mostrando si el algoritmo eleva al cuadrado, o eleva al cuadrado y multiplica.
6. Revise el rastro: La tabla paso a paso muestra cada cálculo intermedio, y la comparación de eficiencia muestra qué tan rápida es la exponenciación binaria frente a la multiplicación repetida ingenua.

Por qué la exponenciación binaria es rápida

Considere calcular \(2^{1000} \bmod 13\). El enfoque ingenuo requiere 999 multiplicaciones. La exponenciación binaria convierte 1000 a binario (1111101000), que tiene 10 bits. Necesita como máximo 9 cuadrados más unas pocas multiplicaciones por cada bit '1' — aproximadamente 15 operaciones en total. Eso es aproximadamente un 98.5% menos operaciones. Para exponentes de escala criptográfica con cientos de dígitos, la diferencia es astronómica: el método binario toma miles de operaciones donde el ingenuo requeriría más operaciones que átomos en el universo.

Preguntas frecuentes