Realizar la operación de elevar un número a una cierta potencia y después aplicarle la operación módulo puede ser algo fácil o difícil de hacer dependiendo tanto del exponente.

Por ejemplo:

Elevar 5 a la potencia 3 en Z₂₇

5³ = 125 ≡ 17 mod 27

es algo fácil de calcular porque el exponente es pequeño.

Ahora elevamos 5 a la potencia 20 en Z₂₇

5²¹ = 476,837,158,203,125 ≡ 17 mod 27

y notamos que se vuelve más difícil de hacer.

---

Un método muy eficaz y rápido para realizar una exponenciación modular con exponentes muy grandes es la Exponenciación Modular Binaria

Este algoritmo hace uso de solo dos operaciones:

• Elevar al cuadrado (SQ) el resultado actual.
• Multiplicar (MUL) el resultado actual por el elemento base.

Este algoritmo está basado en escanear el bit del exponente desde la izquierda (el bit más significativo) a la derecha (el bit menos significativo). En cada iteración, es decir, por cada bit del exponente, el resultado actual se eleva al cuadrado. Si y solo si el bit del exponente escaneado actualmente tiene el valor de 1, una multiplicación del resultado actual por la base es ejecutada después de la elevación al cuadrado. Después de cada paso se aplica la operación módulo para mantener el resultado intermedio pequeño.

Ahora se explicará con el ejemplo anterior.

En primer se mostrará la representación binaria del exponente:

5²¹ = 5¹⁰¹⁰¹ = 5^{(h₄ h₃ h₂ h₁ h₀)}

El algoritmo escanea los bits del exponente empezando por la izquierda con h₄ y finalizando con el bit más a la derecha h₀.

Paso	Desarrollo	Operaciones	Resultado
#0	5 = 512	Ajuste inicial, bit escaneado: h4 = 1	5 mod 27
#1a	(51)2 = 52 = 5102	SQ, bit scaneado: h3	52 ≡ 25 mod 27
#1b		no MUL, ya que h3 = 0
#2a	(52)2 = 54 = 51002	SQ, bit scaneado: h2	252 ≡ 4 mod 27
#2b	54*5 = 55 = 51012	MUL, ya que: h2 = 1	4 * 5 ≡ 20 mod 27
#3a	(55)2 = 510 = 510102	SQ, bit scaneado: h1	202 ≡ 22 mod 27
#3b		no MUL, ya que h1 = 0
#4a	(510)2 = 520 = 5101002	SQ, bit scaneado: h0	222 ≡ 25 mod 27
#4b	520*5 = 521 = 5101012	MUL, ya que: h0 = 1	25 * 5 ≡ 17 mod 27

---

Referencias

1. Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.