14/12/2018, 11:02:56 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Generador para campos finitos  (Leído 4514 veces)
0 Usuarios y 1 Visitante están viendo este tema.
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« : 04/02/2017, 03:09:48 pm »

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 [texx]Z_{13}[/texx], 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([texx]2^8[/texx]) 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([texx]2^8[/texx]).

Muchas gracias de antemano y pido disculpas por la torpeza del redactado
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.869



Ver Perfil
« Respuesta #1 : 04/02/2017, 06:49:57 pm »

Hola AJMurphy.

 Me gustaría saber la definición que tienes para el campo [texx]GF(2^{8}).[/texx] 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 [texx]\mathbb{Z}_{p}[/texx]). Sin embargo cuando tenemos un número primo [texx]p[/texx] el campo [texx]GF(p^{n})[/texx] es una extensión de grado [texx]n[/texx] del campo [texx]GF(p)[/texx] (o [texx]\mathbb{Z}_{p}[/texx] ó [texx]\mathbb{F}_{p}[/texx] dependiendo de la notación que se use).

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

 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) [texx]GF(2^{8})^{*}=GF(2^{8})\setminus\{0\},[/texx] que en nuestro caso es un grupo cíclico de [texx]255[/texx] elementos. Por ser un grupo cíclico, [texx]GF(2^{8})^{*}[/texx] es generado por algún elemento (que no es [texx]1[/texx]), pero encontrarlo explícitamente no es trivial.

Saludos,

Enrique.
En línea
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« Respuesta #2 : 04/02/2017, 10:06:36 pm »

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([texx]2^8[/texx]) 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 [texx]g(x)[/texx] es de la forma [texx]x^8 + x^4 + x^3 + x + 1[/texx].
(7) Entiendo que para obtener el 201 tengo que hacer 149 por [texx]3^n/g(x)[/texx].

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

Muchas gracias por tu tiempo, y espero haber sabido explicarme.
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.869



Ver Perfil
« Respuesta #3 : 07/02/2017, 05:56:25 pm »

Hola AJMurphy.

 No conozco el algoritmo del que hablas. Como te dije antes, [texx]GF(2^{8})[/texx] es un campo (o cuerpo) que tiene [texx]2^{8}=256[/texx] 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 [texx]GF(2^{8})^{*}.[/texx] Respecto a lo del "tercer" elemento que mencionas, en principio los elementos de [texx]GF(2^{8})^{*}[/texx] 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 [texx]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}[/texx]   y   [texx]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}[/texx] de [texx]GF(2^{8})^{*},[/texx] para encontrar el elemento [texx]f_{1}(x)\cdot f_{2}(x)\in GF(2^{8})^{*}[/texx] tenemos que multiplicar los polinomios de la manera usual y luego encontrar el residuo de esa multiplicación al dividirla por [texx]g(x)=x^{8}+x^{4}+x^{3}+x+1[/texx] (que es el polinomio que estás usando para construir [texx]GF(2^{8})^{*}[/texx]).

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

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

Saludos,

Enrique.
En línea
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #4 : 23/02/2017, 02:38:00 pm »

Hola.
 
Hay una manera de ordenar polinomios de característica [texx]p[/texx] que es bastante estándar y en el caso de [texx]p=2[/texx], resulta muy simple. Creo que la tabla es bastante elocuente en cuanto a la construcción de los polinomios.
Editado (me comí un bit). :sonrisa:
 \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 [texx]x+1[/texx].
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.
En línea

Eram quod es, eris quod sum.
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« Respuesta #5 : 23/02/2017, 07:07:13 pm »

Si, efectivamente esto es así.

Gracias
En línea
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #6 : 23/02/2017, 07:56:28 pm »

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 [texx]\mu[/texx] de Möbius.

Saludos.

 
En línea

Eram quod es, eris quod sum.
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« Respuesta #7 : 25/02/2017, 01:56:55 pm »

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.
En línea
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #8 : 26/02/2017, 06:29:38 pm »

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:

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

Construimos un conjunto con todos los elementos de [texx]D255[/texx] que no sean un divisor de ninguno de los elementos de  [texx]m255[/texx], 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 [texx]\Phi_{255}[/texx], se pueden factorizar  en polinomios de grado 8 sobre  [texx]\mathbb{Z}_2[X][/texx]
Los grados de [texx]\Phi_{17},\,\Phi_{51},\Phi_{85},\Phi_{255}[/texx] son:
\[[\varphi(17),\,\varphi(51),\,\varphi(85),\varphi(255)]=[16,32,64,128]\]
Y estos polinomios serán irreducibles sobre  [texx]\mathbb{Z}_2[X][/texx]

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

Si [texx]g(x)=x^{8}+x^{4}+x^{3}+x+1[/texx] y hallamos el resto de la división [texx]\dfrac{\Phi_{51}}{g(x)}[/texx], vemos que es [texx]0[/texx], 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 [texx]51[/texx], 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 [texx]x+1\in \mathbb{Z}_2[X]/\left \langle g(x) \right \rangle[/texx], utilizando el endomorfismo de frobenius.

En la próxima la seguimos. :sonrisa:

Saludos.

En línea

Eram quod es, eris quod sum.
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #9 : 26/02/2017, 08:14:38 pm »

Hola.

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

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

Como [texx]\psi [/texx] es un endomorfismo,  se tiene

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

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

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

Eram quod es, eris quod sum.
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« Respuesta #10 : 02/03/2017, 08:27:39 am »

Hola,

Para [texx]\Phi_{17}[/texx] el factor es [texx](x+1)^4[/texx]
Para [texx]\Phi_{51}[/texx] el factor es [texx](x+1)^5[/texx]
Para [texx]\Phi_{85}[/texx] el factor es [texx](x+1)^6[/texx]

No consigo entender la división [texx]\displaystyle\frac{\Phi_{51}}{g(x)}[/texx]



En línea
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #11 : 02/03/2017, 10:31:13 am »

Hola:

Una fórmula sencilla para calcular [texx]\Phi_n[/texx] es la siguiente:


[texx]\displaystyle\Phi_n=\prod_{d|n}\left(x^d-1\right)^{\mu\left(\frac{n}{d}\right)}[/texx]

Donde [texx]\mu[/texx] es la función de  Möbius

Para [texx]n=17[/texx], se tiene

[texx]\displaystyle\Phi_{17}=\prod_{d|17}\left(x^{17}-1\right)^{\mu\left(\frac{17}{d}\right)}=\frac{x^{17}-1}{x-1}[/texx]

Luego
[texx]\displaystyle\Phi_{17}=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
[/texx]

Si lo factorizamos en [texx]\mathbb{Z}_2[X][/texx], se tiene
[texx]\Phi_{17}=\left( {{x}^{8}}+{{x}^{5}}+{{x}^{4}}+{{x}^{3}}+1\right) \,\left( {{x}^{8}}+{{x}^{7}}+{{x}^{6}}+{{x}^{4}}+{{x}^{2}}+x+1\right) [/texx]

Si hacemos otro tanto con [texx]\Phi_{51}[/texx], obtenemos
[texx]\Phi_{51}=\left(x^8+x^7+x^4+x^3+x^2+x+1\right){\color{red}\left(x^8+x^4+x^3+x+1\right)}\left(x^8+x^7+x^6+x^5+x^4+x+1\right)\left(x^8+x^7+x^5+x^4+1\right)[/texx]

Saludos.
En línea

Eram quod es, eris quod sum.
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #12 : 02/03/2017, 11:28:17 am »

Hola:

Si se quiere hallar el resto de la división [texx]\dfrac{\Phi_{51}}{g(x)}[/texx] en [texx]\mathbb{Z}_2[X][/texx].

Se halla el resto  [texx]\dfrac{\Phi_{51}}{g(x)}[/texx] en la división ordinaria y se anulan los términos con coeficientes pares.
[texx]\operatorname{remainder}\left(\Phi_{51},g(x)\right)=-42x^7+10x^6+8x^5-54x^4-6x^3+6x^2-26x-10[/texx]. Como se puede observar, obtenemos un polinomio con todos los coeficientes pares, resultando en
[texx]\mathbb{Z}_2[X][/texx]

[texx]\operatorname{remainder}\left(\Phi_{51},g(x)\right)=0[/texx]
 
Es decir [texx]g(x)|\Phi_{51}\text{ en }\mathbb{Z}_2[X] [/texx]

Editado
Hay un software libre para matemática simbólica que se llama wxMaxima. Hay versiones para Windows y para Linux. Si lográs instalarlo en tu P.C., podemos ver funciones, para facilitar los cálculos en estos problemas.
Si querés, abrimos un hilo en "Temas de computación" y vemos como resolver este tipo de problemas, computacionalmente.


Saludos.
En línea

Eram quod es, eris quod sum.
AJMurphy
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6


Ver Perfil
« Respuesta #13 : 04/03/2017, 07:13:45 am »

Hola,

Me parece una buena idea lo de instalar vxMaxima. Hasta el próximo martes no estaré en disposición de hacerlo. Si te parece seguimos el Martes.
En línea
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #14 : 04/03/2017, 09:49:38 am »

Hola.
Hola,

Me parece una buena idea lo de instalar vxMaxima. Hasta el próximo martes no estaré en disposición de hacerlo. Si te parece seguimos el Martes.

Me parece bien que instales wxMaxima. De todos modos, en un rato voy a subir un mensaje, sobre un resumen práctico de lo que vimos. Veremos cómo lo hecho hasta ahora facilita los cálculos, y luego, pasaremos al cálculo numérico puro, donde  los polinomios los transformaremos en números y trabajaremos con operaciones binarias, para hacer los cálculos en forma mecánica. En esa instancia, resolver el problema computacionalmente, es una gran ventaja. En la parte numérica, podríamos utilizar cualquier programa, incluso una planilla de cálculo. Pero un sistema con matemática simbólica, nos servirá para ver el correlato entre cálculo mecánico y teoría pura y dura. Lo que te servirá para implementar tus propios algoritmos. Incluso en campos más grandes, como
 [texx]GF\left(2^{16}\right)[/texx].
Saludos.
En línea

Eram quod es, eris quod sum.
Teón
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.322


C:.J:.T:.


Ver Perfil
« Respuesta #15 : 08/03/2017, 10:29:45 am »

\[
\newcommand{\op}[1]{\operatorname{#1}}
\newcommand{\zpg}[2]{\mathbb{Z}_{#1}\left/\left \langle #2(x) \right \rangle\right.}
\]
Hola:

Algunas cosas a tener en cuenta. Por comodidad, le daremos un nombre al grado de un polinomio y al orden de un elemento, diremos

[texx]\op{deg}(f(x))=n[/texx] si el grado del polinomio [texx]f(x)\text{ es } n[/texx].
[texx]\circ(x)=h[/texx] si el orden del elemento [texx]x\text{ en un cuerpo } K\text{ es }h[/texx].

Como ejemplo, para los [texx]x\text{ y }g(x)[/texx] que mencionamos anteriormente, se tiene
[texx]\op{deg}(g(x))=8\text{ y }\circ(x)=51[/texx].

Por otro lado, los elementos de [texx]\zpg{p}{f},\;\zpg{2}{g}[/texx], en nuestro caso los consideramos como polinomios del tipo [texx]x,\,x+1,x^3+x+1,\dots[/texx], en realidad estos polinomios son clases de equivalencia de polinomios en [texx]\mathbb{Z}_2\left[x\right][/texx], los escribimos como polinomios corrientes, pero cualquiera de los polinomios mencionados, [texx]x^3+x+1[/texx], por ejemplo, podríamos escribirlo como
\begin{equation}\label{pol:equiv}
x^3+x+1+p(x)g(x)\text{ con }p(x)\in \mathbb{Z}_2\left[x\right]
\end{equation}
que representarían el mismo elemento en el campo [texx]\zpg{2}{g}[/texx].

La expresión \eqref{pol:equiv}, será crucial para simplificar los cálculos en productos, divisiones y restos, módulo [texx]g(x)[/texx].

Editado.
También nos resultarán útiles a la hora de realizar cálculos, el endomorfismo  de Frobenius y el grado de x.
Si quisiéramos calcular algo como
[texx](x+1)^{65}[/texx], obtenemos:
\begin{equation}\label{frob:simplif}
(x+1)^{65}=(x+1)^{64+1}=\left(x^{64}+1\right)(x+1)=\left(x^{13}+1\right)(x+1)
\end{equation}

En \eqref{frob:simplif}, como 64 es potencia de 2, se puede aplicar el endomorfismo de Frobenius (se puede pasar adentro del paréntesis) y como [texx]\circ(x)=51[/texx] y [texx]64\equiv 13\mod 51[/texx], se tiene que el 64 se transforma en 13.
Saludos.
En línea

Eram quod es, eris quod sum.
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!