Saltar al contenido
El bit perdido
Newsletter

Exponenciación modular rápida paso a paso: aᵉ mod n

Calcula aᵉ mod n con el método de los cuadrados sucesivos, paso a paso: el exponente en binario, la tabla de cuadrados y las multiplicaciones. Con el atajo de Fermat o de Euler cuando se puede.

Números enteros, también negativos (−5) y grandes (hasta 60 cifras).

Ejemplos:

Ejemplo resuelto paso a paso

3²⁰⁰ mód 13

3200≡9(mod13)3^{200} \equiv 9 \pmod{13}

  1. 1El exponente en binario

    En lugar de multiplicar 33 por sí mismo 200200 veces, escribimos el exponente como suma de potencias de 22 (sus cifras en binario). Así bastan unas pocas multiplicaciones.

    200=(11001000)2=27+26+23200 = (11001000)_2 = 2^{7} + 2^{6} + 2^{3}

  2. 2Cuadrados sucesivos

    Cada potencia es el cuadrado de la anterior, reducido módulo 1313 (así los números nunca crecen). Solo nos sirven las filas con cifra binaria 11.

    ibit32i mod 130031≡31032≡32=920322≡92=81≡331323≡32=940324≡92=81≡350325≡32=961326≡92=81≡371327≡32=9\begin{array}{c|c|l} i & \text{bit} & 3^{2^i} \bmod 13 \\ \hline 0 & 0 & 3^{1} \equiv 3 \\ 1 & 0 & 3^{2} \equiv 3^2 = 9 \\ 2 & 0 & 3^{2^{2}} \equiv 9^2 = 81 \equiv 3 \\ 3 & 1 & 3^{2^{3}} \equiv 3^2 = 9 \\ 4 & 0 & 3^{2^{4}} \equiv 9^2 = 81 \equiv 3 \\ 5 & 0 & 3^{2^{5}} \equiv 3^2 = 9 \\ 6 & 1 & 3^{2^{6}} \equiv 9^2 = 81 \equiv 3 \\ 7 & 1 & 3^{2^{7}} \equiv 3^2 = 9 \end{array}

  3. 3Multiplicamos las que hacen falta

    Por las propiedades de las potencias, 327+26+233^{2^{7} + 2^{6} + 2^{3}} es el producto de las filas marcadas. Multiplicamos de dos en dos y reducimos módulo 1313 cada vez.

    9⋅3=27≡11⋅9=9\begin{aligned} & 9 \cdot 3 = 27 \equiv 1 \\ & 1 \cdot 9 = 9 \end{aligned}

  4. 4Resultado

    Hemos hecho 99 multiplicaciones en lugar de 199199.

    3200≡9(mod13)3^{200} \equiv 9 \pmod{13}

  5. 5Otra forma: el pequeño teorema de Fermat

    Como 1313 es primo y no divide a 33, Fermat dice que 312≡1(mod13)3^{12} \equiv 1 \pmod{13}. Dividimos el exponente entre 1212: 200=16⋅12+8200 = 16 \cdot 12 + 8. A mano, es el camino más corto, y da lo mismo.

    3200=(312)16⋅38≡116⋅38≡9(mod13)3^{200} = \left(3^{12}\right)^{16} \cdot 3^{8} \equiv 1^{16} \cdot 3^{8} \equiv 9 \pmod{13}

La idea

Queremos ae mod na^e \bmod n sin calcular aea^e. Escribimos el exponente en binario, calculamos los cuadrados sucesivos

a, a2, a4, a8, …(modn)a,\ a^2,\ a^4,\ a^8,\ \dots \pmod{n}

(cada uno es el cuadrado del anterior, reducido módulo nn) y multiplicamos solo los que corresponden a las cifras 11 del exponente.

Un atajo: Fermat y Euler

Si mcd⁡(a,n)=1\operatorname{mcd}(a,n)=1, entonces aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod{n} (para nn primo, φ(n)=n−1\varphi(n)=n-1: Fermat). Así el exponente se puede sustituir por e mod φ(n)e \bmod \varphi(n) antes de empezar.

Un ejemplo completo

Calculemos 345 mod 173^{45}\bmod 17. En binario, 45=1011012=32+8+4+145=101101_2=32+8+4+1. Los cuadrados sucesivos módulo 1717:

kk32k3^{2^k}módulo 1717
003333
11323^299
2292=819^2=811313
33132=16913^2=1691616
44162=25616^2=25611
55121^211

Multiplicamos los de 1,4,8,321,4,8,32 (las cifras 11 del exponente):

345≡3⋅13⋅16⋅1=624≡12(mod17).3^{45}\equiv3\cdot13\cdot16\cdot1=624\equiv12\pmod{17}.

Con el atajo: como 1717 es primo, 316≡13^{16}\equiv1, y 45≡13(mod16)45\equiv13\pmod{16}, así que 345≡313=38⋅34⋅3≡16⋅13⋅3≡123^{45}\equiv3^{13}=3^{8}\cdot3^{4}\cdot3\equiv16\cdot13\cdot3\equiv12. Coincide.

Errores típicos

  • No reducir en cada paso: se obtienen números enormes y se pierde la gracia del método.
  • Reducir el exponente módulo nn en lugar de módulo φ(n)\varphi(n): para n=17n=17 el exponente se reduce módulo 1616, no módulo 1717.
  • Aplicar Fermat o Euler cuando mcd⁡(a,n)≠1\operatorname{mcd}(a,n)\ne1: el atajo falla.
  • Multiplicar todos los cuadrados, en vez de solo los de las cifras 11 del binario.

Dónde se usa

Es la operación central de RSA (cifrar y descifrar son potencias modulares con exponentes de cientos de cifras) y del intercambio de claves de Diffie-Hellman. También se usa para las pruebas de primalidad.

Preguntas frecuentes

¿Por qué no se calcula primero aᵉ y luego se divide?

Porque aᵉ puede tener millones de cifras. Con los cuadrados sucesivos se reduce módulo n en cada paso y los números nunca pasan de n², así que el cálculo es rápido incluso con exponentes de cientos de cifras.

¿Cuántas multiplicaciones hacen falta?

Del orden del número de cifras binarias del exponente: unas log₂(e) cuadraturas más, como mucho, otras tantas multiplicaciones. Para e = 45 (6 cifras en binario) son menos de 12.

¿Qué dice el pequeño teorema de Fermat?

Si p es primo y p no divide a a, entonces a^(p−1) ≡ 1 (mod p). Por eso el exponente se puede reducir módulo p − 1.

¿Y si el módulo no es primo?

Se usa el teorema de Euler: si mcd(a, n) = 1, entonces a^φ(n) ≡ 1 (mod n), y el exponente se reduce módulo φ(n). Si mcd(a, n) ≠ 1, el atajo no vale y hay que usar los cuadrados sucesivos.

¿Cómo se halla la última cifra de una potencia?

Calculando la potencia módulo 10. Por ejemplo, 7 elevado a 4 es 2401 ≡ 1 (mod 10), así que las potencias de 7 repiten la última cifra con periodo 4: 7, 9, 3, 1.

Otras herramientas

Para leer