Autor Tema: Generador para campos finitos

0 Usuarios y 1 Visitante están viendo este tema.

04 Febrero, 2017, 07:09 pm
Leído 16169 veces

AJMurphy

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Hola, a ver si alguien puede ayudarme.

Según tengo entendido, un generador  es un elemento cuyas sucesivas potencias generan todos los elementos del campo. Para un campo \( Z_{13} \), por ejemplo, que contendría los enteros positivos comprendidos entre el 1 y el 13, el generador sería 2, ya que 2 elevado a las potencias del 1 al 13, modulo 13, generaría todos los elementos del campo.

Esto hasta aquí creo que lo entiendo. Ahora bien, me dicen tambien que en un campo GF(\( 2^8 \)) uno de los posibles generadores es el 3, ya que elevado a sus potencias, modulo 256,  generaría los elementos del 1 al 255. Y esto es lo que ya no entiendo.

Me gustaría, si es posible, que alguien pudiera ponerme un ejemplo muy sencillo de cómo las potencias de 3 generan los 255 números del campo GF(\( 2^8 \)).

Muchas gracias de antemano y pido disculpas por la torpeza del redactado

04 Febrero, 2017, 10:49 pm
Respuesta #1

EnRlquE

  • Lathi
  • Mensajes: 5,907
  • País: br
  • Karma: +0/-0
  • Sexo: Masculino
Hola AJMurphy.

 Me gustaría saber la definición que tienes para el campo \( GF(2^{8}). \) Pues me parece que estás pensando que sus elementos son números naturales (o clases de números naturales como en el caso de \( \mathbb{Z}_{p} \)). Sin embargo cuando tenemos un número primo \( p \) el campo \( GF(p^{n}) \) es una extensión de grado \( n \) del campo \( GF(p) \) (o \( \mathbb{Z}_{p} \) ó \( \mathbb{F}_{p} \) dependiendo de la notación que se use).

 Resumiendo un poco \( GF(p^{n}) \) puede ser visto como el cociente \( GF(p)[ x]/\langle f(x)\rangle \) donde \( f(x) \) es un polinomio irreducible de grado \( n \) en \( GF(p). \) En nuestro caso \( 3\in GF(2^{8}) \) se identifica naturalmente con \( 1 \).

 Por otro lado, con lo de generador tal vez te estés refiriendo al generador o elemento primitivo del grupo cíclico (con la multiplicación del cuerpo) \( GF(2^{8})^{*}=GF(2^{8})\setminus\{0\}, \) que en nuestro caso es un grupo cíclico de \( 255 \) elementos. Por ser un grupo cíclico, \( GF(2^{8})^{*} \) es generado por algún elemento (que no es \( 1 \)), pero encontrarlo explícitamente no es trivial.

Saludos,

Enrique.

05 Febrero, 2017, 02:06 am
Respuesta #2

AJMurphy

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Hola Enrique, muchas gracias por contestarme y perdona mi torpeza, pero mis conocimientos matemáticos son mas bien escasos.

Te explico:
(1) Estoy trabajando en criptografía, concretamente con el algoritmo AES-128.
(2) Una de las especificaciones del algoritmo es la de generar una tabla de multiplicativos inversos.
(3) Si lo he entendido bien, el campo GF(\( 2^8 \)) contiene 255 elementos, del 1 al 255. A este campo voy a llamarle primera tabla
(4) Para obtener los inversos multiplicativos primero tengo que generar una segunda tabla tambien con 255 elementos, y que se obtiene multiplicando cada uno de los elementos de la primera tabla por las potencias del generador (¿raíz primitiva?), en este caso 0x03.
(5) Tengo la primera tabla y la segunda tabla. Para el numero 149 de la primera tabla, por ejemplo, le corresponde el numero 201 de la segunda tabla.
(6) El polinomio irreducible \( g(x) \) es de la forma \( x^8 + x^4 + x^3 + x + 1 \).
(7) Entiendo que para obtener el 201 tengo que hacer 149 por \( 3^n/g(x) \).

El problema que tengo es que no se como calcular el valor de n.

Muchas gracias por tu tiempo, y espero haber sabido explicarme.

07 Febrero, 2017, 09:56 pm
Respuesta #3

EnRlquE

  • Lathi
  • Mensajes: 5,907
  • País: br
  • Karma: +0/-0
  • Sexo: Masculino
Hola AJMurphy.

 No conozco el algoritmo del que hablas. Como te dije antes, \( GF(2^{8}) \) es un campo (o cuerpo) que tiene \( 2^{8}=256 \) elementos. Yo creo que te estás refiriendo al conjunto de los elementos no nulos de este campo, que en mi anterior mensaje denoté por \( GF(2^{8})^{*}. \) Respecto a lo del "tercer" elemento que mencionas, en principio los elementos de \( GF(2^{8})^{*} \) no tienen un orden específico que nos permita decir este es el primer elemento, este el segundo y así sucesivamente. Tal vez en la implementación del algoritmo que mencionas se establezca una forma de ordenar los elementos del campo de forma que sepamos sin duda quién es el tercer elemento, pero lo desconozco, así que no sé cuál es el tercer elemento (ni el 149 ni el 201) al que te refieres.

 Ten presente que si tenemos dos elementos \( f_{1}(x)=a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x^{1}+a_{0} \)   y   \( f_{2}(x)=b_{7}x^{7}+b_{6}x^{6}+b_{5}x^{5}+b_{4}x^{4}+b_{3}x^{3}+b_{2}x^{2}+b_{1}x^{1}+b_{0} \) de \( GF(2^{8})^{*}, \) para encontrar el elemento \( f_{1}(x)\cdot f_{2}(x)\in GF(2^{8})^{*} \) tenemos que multiplicar los polinomios de la manera usual y luego encontrar el residuo de esa multiplicación al dividirla por \( g(x)=x^{8}+x^{4}+x^{3}+x+1 \) (que es el polinomio que estás usando para construir \( GF(2^{8})^{*} \)).

 Entonces si sabemos quién es explicitamente el "tercer elemento" de \( GF(2^{8})^{*}, \) llamémoslo \( h(x) \) por ejemplo, una forma de verificar que \( h(x) \) genera \( GF(2^{8})^{*} \) es hacer una lista de todos los elementos \( h(x), \) \( [h(x)]^{2}:=h(x)\cdot h(x), \) etc. hasta llegar a la potencia \( [h(x)]^{255} \) y finalmente comprobar que todos estos elementos son diferentes.

 Espero que esto que haya ayudado un poco, si tienes alguna dificultad, pregunta.

Saludos,

Enrique.

23 Febrero, 2017, 06:38 pm
Respuesta #4

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.
 
Hay una manera de ordenar polinomios de característica \( p \) que es bastante estándar y en el caso de \( p=2 \), resulta muy simple. Creo que la tabla es bastante elocuente en cuanto a la construcción de los polinomios.
Editado (me comí un bit). :)
 \begin{array}{|c|c|l|}
\hline
0&00000000&0\\ \hline
1&00000001&1\\ \hline
2&00000010&x\\ \hline
3&00000011&x+1\\ \hline
4&00000100&x^2\\ \hline
5&00000101&x^2+1\\ \hline
6&00000110&x^2+x\\ \hline
\vdots&\vdots&\vdots\\ \hline
255&11111111&x^7+x^6+x^5+x^4+x^3+x^2+x+1\\ \hline
\end{array}

Si es así como los ordenan en tu curso, resultaría que el tercer elemento  de un cuerpo de 256 elementos (255 el grupo multiplicativo) es el polinomio \( x+1 \).
Si ese es el caso, podemos seguir hablando, porque lo que sigue necesita de algunos conceptos no demasiado inmediatos.

Como cosa curiosa, de la tabla se desprende, que tanto el orden como la suma de estos polinomios, no dependen del polinomio irreducible, el cual es imprescindible para el producto.

Saludos.
Eram quod es, eris quod sum.

23 Febrero, 2017, 11:07 pm
Respuesta #5

AJMurphy

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Si, efectivamente esto es así.

Gracias

23 Febrero, 2017, 11:56 pm
Respuesta #6

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola AJMurphy:

Si, efectivamente esto es así.

Gracias

Entonces empezamos bien, veamos si conocés algunos conceptos, para ver si abordamos el tema utilizándolos, o si los tenemos que definir.
¿De todo esto qué conocés?

  • Endomorfismo de Frobenius.
  • Polinomios ciclotómicos.
  • Función aritmética \( \mu \) de Möbius.

Saludos.

 
Eram quod es, eris quod sum.

25 Febrero, 2017, 05:56 pm
Respuesta #7

AJMurphy

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, la verdad es que no conozco ninguno de estos conceptos. Tal vez tenga que invertir algo de tiempo en profundizar sobre estos tres temas antes de continuar.

26 Febrero, 2017, 10:29 pm
Respuesta #8

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Releer este mensaje, porque corregí algunos errores importantes.

Hola.
No importa, mientras vos investigás un poco sobre esos conceptos, vamos resolviendo el problema.

Primero buscamos los divisores de 255

\[D255=\{3,5,15,17,51,85\}\]

También hallamos los números de la forma:

\( 2^n-1\text{ con }n=1\dots 7  \), con lo que obtenemos el conjunto
\[m255=\{1,3,7,15,31,63,127\}\].

Construimos un conjunto con todos los elementos de \( D255 \) que no sean un divisor de ninguno de los elementos de  \( m255 \), obtenemos

\[R255=\{17,51,85\}\]

Estos números nos indican que los polinomios ciclotómicos

\[\Phi_{17},\,\Phi_{51},\Phi_{85}\]

Editado.
Además de \( \Phi_{255} \), se pueden factorizar  en polinomios de grado 8 sobre  \( \mathbb{Z}_2[X] \)
Los grados de \( \Phi_{17},\,\Phi_{51},\Phi_{85},\Phi_{255} \) son:
\[[\varphi(17),\,\varphi(51),\,\varphi(85),\varphi(255)]=[16,32,64,128]\]
Y estos polinomios serán irreducibles sobre  \( \mathbb{Z}_2[X] \)

Editado.
Si \( g(x) \) es un polinomio irreducible  de grado 8 sobre \( \mathbb{Z}_2[X] \), entonces debe ser un factor de uno y sólo uno de los polinomios ciclotómicos \( \Phi_{17},\,\Phi_{51},\Phi_{85},\Phi_{255} \) ;

Si \( g(x)=x^{8}+x^{4}+x^{3}+x+1 \) y hallamos el resto de la división \( \dfrac{\Phi_{51}}{g(x)} \), vemos que es \( 0 \), es decir:
\[g(x)\equiv 0\mod \Phi_{51}\].
Editado.
Todo esto nos sirve para saber que el polinomio
\[x\in \mathbb{Z}_2[X]/\left \langle g(x) \right \rangle\] tiene grado \( 51 \), es decir
\[x^{51}=1\land x^k\neq 1\text{ si } 0<k<51\]

Con todo esto, se nos facilita la tarea de hallar el grado de \( x+1\in \mathbb{Z}_2[X]/\left \langle g(x) \right \rangle \), utilizando el endomorfismo de frobenius.

En la próxima la seguimos. :)

Saludos.

Eram quod es, eris quod sum.

27 Febrero, 2017, 12:14 am
Respuesta #9

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

El endomorfismo de Frobenius para \(  \mathbb{Z_p}\left[x\right]  \) es la función

\(  \psi: \mathbb{Z_p}\left[x\right]\to \mathbb{Z_p}\left[x\right]\text{ donde } \psi(a)=a^p \)

Como \( \psi  \) es un endomorfismo,  se tiene

 \( \psi(a+b)=\psi(a)+\psi(b)\land \psi(ab)=\psi(a)\psi(b),\,\forall a,b\in \mathbb{Z_p}\left[x\right]  \)

En particular
\( (x+1)^p=\left(x^p+1\right) \)
Es fácil ver que \( (x+1)^{p^k}=\left(x^{p^k}+1\right) \)
En nuestro caso \( p=2 \), si queremos saber cuanto vale \( (x+1)^{17} \) se tiene
\( 17=16+1 \) luego
\( (x+1)^{17}=(x+1)^{16+1}=(x^{16}+1)(x+1) \), si esto se resuelve en
\( \mathbb{Z}_2\left[X\right]/\left \langle g(x) \right \rangle \), se obtiene \( (x+1)^{17}=x^7+x^6-x^5+1 \).

Si comprobamos que \( (x+1)^{51}\neq 1\land (x+1)^{85}\neq 1 \), se tiene que \( x+1 \)
es un elemento primitivo en \( \mathbb{Z}_2\left[X\right]/\left \langle g(x) \right \rangle \).
Saludos.
Eram quod es, eris quod sum.