Criptografía 101 – Fundamentos Matemáticos (II)

04/12/2017Artículo original

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:

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:

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

  Telefónica abrirá centros 42 en Barcelona, Málaga, Valencia y Vizcaya, para aprender programación gratis y sin experiencia previa

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

  FRIKADAS: Orecchio, comunicación no verbal con las orejas para gente con movilidad reducida

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 = 1A = 2es k_0 == 1? sí -> b = 2Desde 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 = 2devuelve 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\):

Criptografía 101 &#8211; Fundamentos Matemáticos (II)

Criptografía 101 &#8211; Fundamentos Matemáticos (II)

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:

defpowerModInt(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=1ifk==0:returnbA=a# If the least significant bit is 1, $a^1 = a$if1&k:b=ak=k>>1whilek:A=(A**2)%nif1&k:b=(b*A)%nk=k>>1returnb

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

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

  • \(<1> = \{ 1 \}\), ya que \(\forall k \in\mathbb Z, 1^k = 1\)
  • \(<2> = \{ 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 3\} = \{ 1, 2, 3, 4 \}\)
  • \(<3> = \{ 3^0, 3^1, 3^2, 3^3\} = \{ 1, 2, 3, 4 \}\)
  • \(<4> = \{ 4^0, 4^1, 4^2, 4^3 \} = \{ 1, 4 \}\)
  Creando aplicaciones Linux con Xamarin y Xamarin.Forms

Si nos fijamos, tanto como generan por completo \(\mathbb Z_5\), estos elementos se llaman primitivos. Particularmente, 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

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad