Autor

Alejandro Alcalde

Graduado en Ingeniería Informática en la ETSIIT, Granada. Creador de El Baúl del Programador

Más artículos de Alejandro Alcalde

Este artículo es parte del curso de Introducción a la Criptografía, el código está disponible en elbaulp/cripto, también hay una tabla de contenidos.

Cálculo de potencias

Queremos ahora, dados a, m y n calcular \(a^m\bmod n\), pero de forma eficiente, para ello definiremos el teorema de Fermat:

Sean \(a,n \in \mathbb N\), si \(mcd(a,n) = 1\), \(a^{\phi(n)} \equiv 1\pmod n\)

Veamos algunos ejemplos. En \(\mathbb Z_5,\ \phi(5) = 4\), luego, por el teorema de Fermat, tenemos que \(1^{4} = 2^{4} = 3^{4} = 4^{4} = 1\). En \(\mathbb Z_{53}, \phi(53) = 52\), para calcular \(7^{111}\), como \(mcd(7, 53) = 1\) entonces \( 7^{52} = 1\), luego \(7^{52\cdot 2} = 7^{104} = 1\) y por tanto \(7^{111} = 7^7 = 29\).

Un caso particular del teorema de Fermat, es el teorema Pequeño de Fermat:

Sea p primo, \(a \in \mathbb N:\ 1 \leq a \leq p-1\) entonces \(a^{p-1} \equiv 1\pmod p\)

Como consecuencia a esto se tiene que \(a^{p} \equiv a\pmod p\). Veamos algunos ejemplos:

Calculemos las unidades de \(\mathbb Z_4\), que son \(\mathcal U(\mathbb Z_4) = \{1,3\}\), sabemos que únicamente tiene dos unidades, porque \(\phi(4) = \phi(2^2) = 2\), y particularmente son el 1 y el 3, porque cumplen que \(1^2 = 3^2 = 1\). Más arriba vimos que en \(\mathbb Z_5,\ \phi(5) = 4\) y por tanto todos sus elementos tienen inverso, comprobemos que también se cumple una de las variantes del teorema Pequeño de Fermat en \(\mathbb Z_5\). El teorema dice \(a^{p} \equiv a\pmod p\), como vemos, en \(Z_5, 0^5 = 0, 1^5 = 1, 2^5 = 2, 3^5 = 3, 4^5 = 4\).

Algoritmo para el cálculo de potencias

Uno de los algoritmos usados para el cálculo de potencias modulares es el siguiente:


  1. Fijar b = 1, Si k = 0 devolver b.
  2. A = a
  3. Si k_0 = 1 entonces b = a
  4. Para cada i desde 1 a t repetir:
     1. A = A * A modulo n.
     2. Si k_i = 1 entonces b = A * b modulo n
  5. Devolver b

Este algoritmo se basa en el hecho de que se puede representar el exponente en representación binaria. La representación binaria de k viene dada por \(\sum_{i=0}^t k_i 2^i\), donde cada \(k_i\in \{0, 1\}\). Quizá con esta notación no te resulte familiar, pero no es más que la forma abreviada de la más conocida, por ejemplo, 5 en binario es \(1\cdot 2^0 + 0\cdot 2^1 + 1\cdot 2^2\). Sabiendo esto, entonces

$$a^k = \prod_{i=0}^t a^{k_i 2^i} = (a^{2^0})^{k_0}(a^{2^1})^{k_1}\cdots(a^{2^t})^{k_t}$$

Si analizas un poco la expresión de arriba, cuando \(k_i = 0\) todo el término \((a^{2^i})^{k_i} = 1\), lo cual implica que ese cálculo no va a cambiar el resultado, porque estás multiplicando por 1.

Con este apunte, leer el algoritmo es sencillo. Recibe un número entero y otros dos números, k,n > 0 y calcula \(a^{k} \pmod n\). Si k==0 no es necesario hacer ningún cálculo y simplemente devolvemos 1, ya que cualquier cosa elevada a cero es 1. En el paso 3, si \(k_0\) (el bit menos significativo de la representación binaria) es 1, luego \((a^{2^0})^{k_0} = a\), de lo contrario b = 1, ya que estás elevando a 0, y cualquier número elevado a 0 es 1. El siguiente paso es iterar sobre los bits restantes de k, es decir, desde \(k_1 \dots k_t\). Básicamente se repite el mismo proceso, se eleva al cuadrado A (corresponde con esta parte de la expresión \((a^2\)), y si el bit \(k_i = 1\) multiplicas \((a^{2^i})^{1}\) por b, si \(k_i = 0\) no hace falta hacer nada, ya que toda la expresión \((a^{2^i})^{0} = 1\). Una vez recorrida la representación binaria de k, devolvemos b.

Para entenderlo mejor, imagina que quieres calcular \(2^5\pmod 5\). El primer paso es representar el exponente en binario, \(5 = 101_b\), sigue los pasos del algoritmo, donde a = 2, k = 5 y n = 5:


b = 1
A = 2
es k_0 == 1? sí -> b = 2
Desde k_1 hasta k_t:
   A = A * A mod n -> 2 * 2 mod 5 = 4
   es k_1 == 1? no
   A = A * A mod n -> 4 * 4 mod 5 = 1
   es k_2 == 1? sí -> b = A * b mod n -> b = 1 * 2 mod 5 = 2
devuelve b, que es 2

He intentado hacer dos representaciones visuales de cómo funciona, supón que quieres calcular \(2^7 \pmod 5\) y \(2^{11} \pmod 5\):

Calcular potencias modulares criptografía

Espero que con este ejemplo te haya quedado claro cómo funciona el algoritmo. Lo he implementado en python, el código fuente está disponible en github:

def powerModInt(a,k,n):
  """
      @input a in $Z_n$ and integers 0 <= k <= n
      @output a to the power of k mod n ($a^k mod n$)
  """
  b = 1
  if k == 0:
      return b
  A = a
  # If the least significant bit is 1, $a^1 = a$
  if 1 & k:
      b = a
  k = k >> 1
  while k:
      A = (A**2) % n
      if 1 & k:
          b = (b * A) % n
      k = k >> 1
  return b

Orden

Definiremos el orden de un número como \[ord(a) = min(k\ \in \mathbb N\backslash 0\:a^k=1)\] es decir, el número mínimo al que hay que elevar a para que sea igual a 1. Así, por ejemplo, en \(\mathbb Z_5\), tenemos los siguientes órdenes para sus elementos:

Subgrupos y primitivos

Sea a un elemento de \(\mathbb Z_p\), por ejemplo, \(\lt a> = \{ a^k:\ k\in N \}\) es un subgrupo generado por a.

Por ejemplo, los subgrupos de las unidades de \(\mathbb Z_5\) son:

Si nos fijamos, tanto <2> como <3> generan por completo \(\mathbb Z_5\), estos elementos se llaman primitivos. Particularmente, <a> será primitivo si su orden es máximo, en el caso que nos ocupa, vemos que es cierto, puesto que \(\phi(5)=4, ord(2) = ord(3) = 4\), que es el máximo. Además, el orden de un número establece número de elementos que genera el subgrupo, como ord(2) = ord(3) = 4, sabemos que éstos subgrupos generan 4 elementos, que son el número de unidades de \(\mathbb Z_5\), y por tanto, lo generan completamente. De igual manera, vimos un poco más arriba que ord(4) = 2, y podemos comprobar 4 genera únicamente dos elementos.

Referencias

Todo el código mostrado en los artículos está disponible en github

¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo o comentando abajo.

Quizá también te interese leer...