Autor

Alejandro Alcalde

Data Scientist and Computer Scientist. Creator of this blog.

Más artículos de Alejandro Alcalde | Porfolio

Índice

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:

Entrada: $a\in\mathbb Z_n$, un entero $0 \leq k \lt n$ cuya representación binaria es $\sum_{i=0}^t k_i 2^i$.
Salida: $a^k \pmod n$

  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$:

<figure> <a href="/img/criptografia-101-fundamentos-matematicos-ii-powermodint.png"> <img on="tap:lightbox1" role="button" tabindex="0" layout="responsive" src="/img/criptografia-101-fundamentos-matematicos-ii-powermodint.png" alt="Calcular potencias modulares criptografía" title="Calcular potencias modulares Criptografía" sizes="(min-width: 640px) 640px, 100vw" width="640" height="330"> </img> </a> <figcaption>Calcular potencias modulares criptografía</figcaption> </figure>

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:

$1^1 = 1; ord(1) = 1$, ya que el número mínimo al que hay que elevar 1 para que de 1, es 1.
$2^4 = 1; ord(2) = 4$
$3^4 = 1; ord(3) = 4$
$4^2 = 1; ord(4) = 2$, ya que el número mínimo al que hay que elevar 4 para que de 1, es 2.

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:

$\lt 1> = \{ 1 \}$, ya que $\forall k \in\mathbb Z, 1^k = 1$
$\lt 2> = \{ 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 3\} = \{ 1, 2, 3, 4 \}$
$\lt 3> = \{ 3^0, 3^1, 3^2, 3^3\} = \{ 1, 2, 3, 4 \}$
$\lt 4> = \{ 4^0, 4^1, 4^2, 4^3 \} = \{ 1, 4 \}$

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

Apuntes de la asignatura criptografía del profesor Jesús García Miranda, Escuela Técnica Superior de Ingenierías Informática y de Telecomunicación (ETSIIT), Granada.
Handbook of Applied Cryptography (Discrete Mathematics and Its Applications)

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

Categorías:

seguridad criptografía

Etiquetas:

Quizá también te interese leer...

«« Por qué elimino el perfil de Facebook Índice de Introducción a la Criptografía »»