Estoy dado de dos tablas de multiplicación y adición para un campo finito (es decir, las tablas son diferentes nombres de los elementos del campo) y quiero encontrar el isomorfismo entre las dos representaciones. Una idea es un elemento primitivo del primer campo a un elemento primitivo del segundo campo y definir el resto de la asignación según sus poderes, pero no estoy seguro, además se conservan en este método.
Respuesta
¿Demasiados anuncios?
La siguiente es una recopilación de las ideas publicadas en los comentarios junto con algunos de mis propios pensamientos. Esto es demasiado largo para caber en un comentario, y creo que esto funciona con una complejidad razonable, incluso suponiendo que usted no tiene ninguna otra información disponible de la suma y la multiplicación de las tablas de los dos campos. Soy todo oídos a las sugerencias de mejoras y mejores soluciones. Creo que es muy probable que mi enfoque puede ser mejorado.
- Primero sabemos que la característica $p$ y el grado de extensión de la $n$ sobre el primer campo simplemente por el tamaño de las tablas. Así que en este punto sabemos que ambos campos son isomorfos a $GF(p^n)$, y tienen cíclicos Galois grupos generados por el Frobenius mapa de $F:x\mapsto x^p$. También podemos identificar fácilmente los elementos de la primer campo, como manchado $0$ $1$ es fácil, y la generación de $2=1+1,3=2+1,\ldots,p-1$ también es sencillo.
- Partición de ambos campos en los distintos sindicatos de la órbita bajo el grupo de Galois. La órbita de un elemento $x$ se compone de los elementos de la forma$F^i(x)$$i=0,1,\ldots$. Tenga en cuenta que para algunos entero $d$ tenemos $F^d(x)=x$, y además siempre me pasa que el smalles tal $d$ es un factor de $n$. Aquí el exponente de $F$ indica la iteración, por lo que $F^2(x)=F(F(x))$, $F^3(x)=F(F^2(x))$ et cetera. También tenga en cuenta que en el caso de $p=2$ el Frobenius mapa se acaba de cuadrar, y su valor se puede leer inmediatamente a partir de la tabla de multiplicación. Si quieres pasar menos tiempo con este paso, voy a revelar suficiente para encontrar una órbita de un tamaño máximo $n$ a partir de uno de los campos.
- Siguiente voy a localizar un espacio vectorial (sobre el primer campo) para uno de los campos. Con la partición de paso 2 en la mano (incluso con el alcance descrito en la última frase del paso 2) esto es fácil. Deje $\alpha$ ser un elemento en una órbita de tamaño máximo $n$. A continuación, $\alpha$ genera el campo como una extensión más de la primer campo, y podemos usar $\mathcal{B}=\{1,\alpha,\alpha^2,\ldots,\alpha^{n-1}\}$. La identificación de todos estos elementos utilizando la tabla de multiplicar es sencillo.
- Lo siguiente que describe un método para encontrar las coordenadas de un elemento con respecto a la base $\mathcal{B}$. El método depende del hecho de que la forma bilineal $(x,y)=Tr(xy)$ es no degenerada. Aquí $$ Tr(x)=x+F(x)+F^2(x)+\cdots+F^{n-1}(x)=\sum_{i=0}^{n-1}F^i(x), $$ y (esto es importante) sus valores pertenecen al primer campo, y por lo tanto puede ser identificado. La no degeneración de esta forma bilineal significa que $0$ es el único elemento $y$ con la propiedad: $(x,y)=0$ todos los $x$. Por lo tanto, dado un elemento $\beta$ queremos encontrar elementos $x_i,i=0,\ldots,n-1$ del primer campo que $\beta=\sum_i x_i\alpha^i$. Las coordenadas son la (única) solución del sistema de ecuaciones lineales dado por $$ (\beta\alpha^j)=\sum_i x_i(\alpha^i,\alpha^j), $$ donde $j=0,1,\ldots,n-1$. Este sistema puede ser resuelto, por ejemplo, por eliminación Gaussiana. IOW tiene complejidad polinomial en $n$, por lo que le da una notable mejora a la fuerza bruta de búsqueda de todas las combinaciones - al menos si $n$ es un poco más grande. Si $p^n$ es pequeño, entonces la fuerza bruta puede ser mejor, ya que evitar el cálculo de $n(n+1)/2$ trazas - su llamada. [Edit: no-degeneración de la traza de forma manisfests aquí en la mejor forma de que la matriz de $((\alpha^i,\alpha^j))_{i,j=1}^n$ es no singular.]
- A continuación podemos determinar el polinomio mínimo $m(x)$$\alpha$. Esto es fácil, porque todo lo que tenemos que hacer es aplicar el método de paso de 4 a $\beta=\alpha^n$.
- La tarea pendiente es la de localizar un cero del polinomio $m(x)$ desde el otro campo. Sabemos de antemano que todos los ceros forman un Frobenius órbita de tamaño $n$, por lo que solo necesitamos comprobar tales elementos, un representante de cada órbita hasta tenemos suerte. La construcción de la isomorfismo es entonces fácil.
Realmente espero que no sea algo mejor que el paso 6. Que ha exponencial de la complejidad como una función de la $n$ como se hace el paso 2. Puede estar haciendo los pasos 3 a 5 para ambos campos de ayuda? Sólo necesitamos uno de tamaño completo órbita a hacer los pasos 3 a 5, y un elemento aleatorio es más probable que no que tiene un tamaño completo de la órbita, por lo que puede que no necesitemos la partición completa del paso 2.
Esto no es satisfactorio, así que espero que podamos seguir esto como un esfuerzo de grupo. La principal contribución de mi respuesta es el método de búsqueda de un monomio base y los relacionados con la mínima polinomio mediante el seguimiento de forma.
