• Author / Uploaded
• Maria Lunes

Citation preview

Cuerpos finitos Llorenç Huguet Rotger Josep Rifà Coma Juan Gabriel Tena Ayuso PID_00200953

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de Creative Commons. Podéis copiarlos, distribuirlos y transmitirlos públicamente siempre que citéis el autor y la fuente (FUOC. Fundació per a la Universitat Oberta de Catalunya), no hagáis un uso comercial y no hagáis una obra derivada. La licencia completa se puede consultar en http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

Índice

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.

Existencia y propiedades de los cuerpos finitos . . . . . . . . . . . . . .

7

1.1.

Existencia y construcción de cuerpos finitos . . . . . . . . . . . . . . . . . .

7

1.2.

Estructura aditiva y multiplicativa de un cuerpo finito . . . . . . . .

12

1.2.1.

Representación aditiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.2.2.

Representación multiplicativa . . . . . . . . . . . . . . . . . . . . . . . .

14

2.

Bases de cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.

Computación en cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.

Aritmética en cuerpos finitos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.1.

Multiplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.2.

División . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.1.3.

Exponenciación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.2.

Complejidad de la aritmética en cuerpos finitos . . . . . . . . . . . . . .

23

3.3.

Algoritmos aritméticos en cuerpos finitos . . . . . . . . . . . . . . . . . . . . .

27

Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

CC-BY-NC-ND • PID_00200953

5

Introducción

Los sistemas y protocolos criptográficos que serán objeto de estudio en módulos posteriores utilizan como alfabeto un cuerpo finito o una curva definida sobre ese cuerpo. La necesidad de la estructura de cuerpo obedece a que en dichos sistemas hay que realizar las cuatro operaciones de suma, diferencia, multiplicación y división y obviamente, como siempre en criptografía, este tipo de alfabeto debe ser finito. Los cuerpos finitos han sido estudiados desde hace siglos por diversos matemáticos, en particular Evariste Galois (de hecho son también conocidos como cuerpos de Galois), pero es en los últimos 50 años cuando el interés por estas estructuras ha conocido un crecimiento espectacular, debido a sus aplicaciones en diferentes campos de indudable interés para el mundo industrial y financiero, como son la criptografía o los códigos correctores de errores. La teoría de códigos correctores de errores trata de preservar la calidad de la información cuando es transmitida a través de canales susceptibles de sufrir perturbaciones, que introducen errores en el mensaje transmitido. Un código corrector permite, dentro de ciertos límites, detectar y corregir tales errores. Esta teoría comparte con la criptografía fines (si los códigos correctores tratan de defender la información de la degradación natural la criptografía trata de defenderla de los ataques humanos) y técnicas, en particular diversos sistemas criptográficos (McEliece, Niederreiter), están basados en códigos correctores. Denotaremos Fq a un cuerpo finito con q elementos (algunos autores utilizan la notación GF(q), por Galois field con q elementos). El presente módulo estudia esta estructura matemática, con especial énfasis en los aspectos computacionales de su aritmética.

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

6

Objectivos

En los materiales didácticos de este módulo el estudiante encontrará los contenidos necesarios para alcanzar los objetivos siguientes:

1. Conocer la estructura aditiva y multiplicativa de un cuerpo finito Fq , de q = pm elementos, donde p es un número primo. 2. Saber calcular la tabla de equivalencias polinomial-exponencial y saber calcular en un cuerpo finito Fq dando los resultados en cualquiera de las dos representaciones. 3. Saber reconocer la complejidad computacional de un cálculo en cuerpos finitos. 4. Conocer y saber aplicar los principales algoritmos aritméticos en cuerpos finitos.

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

7

1. Existencia y propiedades de los cuerpos finitos .

En este apartado se muestra para qué valores de q existe un cuerpo finito Fq y cómo construirlo explícitamente y se estudian sus propiedades y estructura.

1.1. Existencia y construcción de cuerpos finitos En primer lugar señalemos el siguiente resultado del teorema 1. . Lectura recomendada

Teorema 1.1 (Teorema de Wedderburn). Todo cuerpo finito es conmutativo (es decir, su multiplicación es conmutativa).

Sobre el teorema de Wedderburn podéis consultar la obra de Lidl y Niederreiter (1997).

. Definición 1.2 (Característica de un cuerpo). La característica de un cuerpo K se define como el mínimo p de los enteros positivos n tales que n · 1 = 1 + 1 + · · · + 1 = 0 (suma de n copias de 1), donde 0 es el elemento neutro de la suma y 1 el elemento neutro del producto en el cuerpo K. Si tal p no existe, como sucede con el cuerpo de los números reales, decimos que K tiene característica 0. Caso contrario p debe ser un número primo (si p = r · s, 1 < r,s < p se tendría que 0 = p · 1 = (r · 1)(s · 1) y uno de los dos factores debería ser cero, en contradicción con la minimalidad de p) y el cuerpo se dice de característica prima p.

Un primer ejemplo de cuerpo finito viene dado por el siguiente resultado. . Proposición 1.3. Para todo número primo p el conjunto Zp de los enteros módulo p, con la suma y producto inducidos por las de Z, constituye un cuerpo conmutativo.

Demostración: Recordemos que el conjunto Zp de los enteros módulo p es el conjunto de clases de equivalencia de números enteros, donde dos enteros x,y son equivalentes si, y solamente si, son congruentes módulo p: x ≡ y (mod p) (es decir x – y es divisible por p). El conjunto Zp tiene cardinal p y un conjunto de representantes viene dado por Fp = {0,1, . . . ,p – 1}.

Observación Existen cuerpos infinitos que no son conmutativos, como el cuerpo de los cuaterniones.

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

8

Las operaciones a + b (mod p) y a · b (mod p) (realizar la suma o producto de a y b en Z , dividir el resultado por p y tomar el resto) dota a este conjunto de estructura de cuerpo: es obvio que (Fp ,+) es un grupo aditivo, con 0 como elemento neutro y opuesto de a ∈ Fp el elemento –a = p – a. Por lo que se refiere a (F∗p = Fp – {0},·) la multiplicación es conmutativa, el elemento 1 actúa como unidad y dado un elemento a ∈ F∗p la existencia de inverso (y un método efectivo de calcularlo) se deduce del algoritmo de Euclides (el cual se describirá a continuación): dado que a y p son coprimos entre sí, existen elementos x,y ∈ Z tales que mcd(a,p) = 1 = ax + py, y por tanto en Fp (nótese que p ≡ 0 (mod p)) ax ≡ 1 (mod p), luego el elemento x (mod p) es el inverso del a. El algoritmo de Euclides (Euclides, libro VII), que permite obtener el máximo

Cuerpo binario

común divisor d de dos números a,b ∈ N, es uno de los algoritmos básicos en matemática computacional. Una modificación - algoritmo de Euclides extendido- permite obtener d como combinación lineal de a y b con coeficientes enteros (Identidad de Bezout):

d = ax + by

(1)

Si p = 2, se tiene el cuerpo con dos elementos F2 = {0,1} base de la computación binaria (las operaciones de cuerpo coinciden con las operaciones lógicas O-exclusivo (XOR) y AND).

Exponemos a continuación el algoritmo de Euclides extendido. . Algoritmo 1.4.

1.

Tomar, como valores iniciales, a0 := a, a1 := b, x0 := 1, x1 := 0, y0 := 0, y1 := 1.

2.

A partir de i := 1, iterar las asignaciones ai+1 := ai–1 – qi ai (calculamos el cociente qi y el residuo ai+1 de la división entre ai–1 y ai ) xi+1 := xi–1 – qi xi (a partir de xi–1 ,xi i qi , calculamos xi+1 ) yi+1 := yi–1 – qi yi (a partir de yi–1 ,yi i qi , calculamos yi+1 ) hasta obtener un residuo ai = 0.

3.

Si an es el primer residuo nulo, entonces d = an–1 = axn–1 + byn–1 .

Ejemplo 1.1. Sean a = 256, b = 96. Aplicando el algoritmo 1.4 se obtiene: a2 = 64, a3 = 32, a4 = 0, x2 = 1, x3 = –1, y2 = –2, y3 = 3. Luego d = a3 = 32 = 256(–1) + 96 · 3. Ejemplo 1.2. Sea p = 7, y el cuerpo F7 = {0,1,2,3,4,5,6}. Para a = 3, b = 6 se tiene 3 + 6 ≡ 2 (mod 7), 3 · 6 ≡ 4 (mod 7) y 3–1 ≡ 5 (mod 7) (nótese que 1 = 1 · 7 – 2 · 3).

Observación El Algoritmo 1.4 puede aplicarse también a dos polinomios a(X),b(X) con coeficientes en un cuerpo K. Ver el ejemplo 1.3.

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

9

Ejemplo 1.3. Calcular el máximo común divisor mcd(P(X),Q(X)) y expresar el resultado como combinación de los polinomios iniciales P(X) y Q(X), donde P(X) y Q(X) son polinomios a coeficientes en F3 : P(X) = X7 + 2X2 + X + 1; Q(X) = X3 + 2X2 . La aplicación del algoritmo de Euclides extendido nos da: a0 = X7 + 2X2 + X + 1; a1 = X3 + 2X2 ; a2 = X + 1; a3 = 1; a4 = 0 q1 = X4 + X3 + X2 + X + 1; q2 = X2 + X + 2 x0 = 1; x1 = 0; x2 = 1; x3 = 2X2 + 2X + 1 y0 = 0; y1 = 1; y2 = 2X4 + 2X3 + 2X2 + 2X + 2; y3 = X6 + 2X5 + X4 + X3 + X2 O sea que, 1 = mcd(P(X),Q(X)) y, además: (X2 + X + 2)P(X) + (X6 + 2X5 + X4 + X3 + X2 )Q(x) = 1

Determinemos ahora para qué otros valores de q, distintos de los primos, existe un cuerpo finito con q elementos. . Proposición 1.5. Sea K = Fq un cuerpo finito con q elementos, con elemento neutro para la adición 0K y elemento unidad para la multiplicación 1K . Existe un primo p tal que K contiene al cuerpo Fp de los enteros módulo p.

Demostración: El cuerpo K no puede tener característica 0 (caso contrario contendría al conjunto infinito {1K ,2 · 1K , · · · ,n · 1K , · · · }). K es pues de característica prima p y contiene al subcuerpo {0K ,1K ,2 · 1K , · · · (p – 1) · 1K } isomorfo al cuerpo Fp de los enteros módulo p. . Corolario 1.6. Sea Fq un cuerpo de característica p. Existe un entero positivo m tal que q = pm .

Demostración: Fq admite una estructura de espacio vectorial sobre su subcuerpo Fp , sea m su dimensión (obviamente finita). Fijada una base cualquiera de este espacio vectorial, Fq se identifica con el conjunto de vectores Fm p , conjunto con cardinal pm . El resultado anterior muestra que el cardinal de un cuerpo finito es siempre potencia de un número primo. El siguiente teorema muestra que para cualquier potencia de un primo existe un cuerpo finito con ese cardinal y que tal cuerpo es esencialmente único. . Definición 1.7 (Clausura algebraica). Sea K un cuerpo. La clausura algebraica de K es un cuerpo que contiene a K, tal que todo polinomio con coeficientes en K tiene todas sus raíces en él y que es minimal con esta propiedad. Tal clausura existe y es única salvo isomorfismo.

Observación El cuerpo C de los números complejos contiene las raíces de todo polinomio con coeficientes en el cuerpo Q de los números racionales. Sin embargo C no es una clausura algebraica de Q ya que no se cumple la condición de minimalidad. La clausura es un subcuerpo de C denominado cuerpo de los números algebraicos.

CC-BY-NC-ND • PID_00200953

10

. Teorema 1.8. Para todo primo p y todo número natural m existe un cuerpo finito con q = pm elementos. Tal cuerpo es único salvo isomorfismo.

Demostración: Sea Fp el cuerpo con p elementos y el polinomio definido sobre este cuerpo: F(X) = Xq – X. Sea R el conjunto de las q raíces de F(X) en una cierta clausura algebraica de Fp (no confundir con las raíces complejas de tal polinomio, nótese que Fp no está contenido en los complejos). Tales raíces son distintas (el polinomio F(X) no tiene raíces múltiples, ya que su derivada no es nula: F ′ (X) = qXq–1 – 1 ≡ –1 (mod p) y por tanto R tiene cardinal q. Ahora bien R es un cuerpo: Sean α,β ∈ R, es decir αq = α, βq = β. Obviamente, entonces (α · β)q = α · β y (suponiendo β 6= 0) (α : β)q = α : β. Pero teniendo en cuenta que en Fp , q ≡ 0, también (α ± β)q = α ± β (pues todos los demás miembros del desarrollo de (a + b)q son múltiplos de p), luego la suma, diferencia, producto y cociente de elementos de R están en R. Sea K otro cuerpo con q elementos. El grupo multiplicativo K∗ = K – {0} tiene cardinal q–1 y por tanto, todo elemento a ∈ K∗ verifica aq–1 = 1K , luego aq = a, ecuación que obviamente también verifica OK . Es decir, los q elementos de K son raíces de Xq – X y por tanto K puede identificarse con R. Habitualmente, en criptografía se utilizan los dos tipos de cuerpos siguientes: 1) Cuerpos binarios F2m , con 2m elementos. 2) Cuerpos Fp , con p elementos y p primo (habitualmente muy grande). El teorema 1.8 demuestra la existencia de un cuerpo finito con q elementos, pero no una construcción explícita. El método siguiente proporciona tal construcción, que es formalmente análoga a la del cuerpo Fp como clases de equivalencia de los enteros módulo p. Sea f (X) = Xm +fm–1 Xm–1 + · · · +f1 X+f0 ∈ Fp [X] un polinomio mónico (coeficiente del término de mayor grado igual a 1) e irreducible, con coeficientes en Fp . En el anillo de polinomios Fp [X] consideremos el conjunto de sus clases de equivalencia módulo f (X). Un conjunto de representantes de estas clases viene dado por el conjunto K de los q = pm polinomios a0 +a1 X+· · ·+am–1 Xm–1 ∈ Fp [X] de grado menor que m (pues todo g(X) ∈ Fp [X] es equivalente al polinomio resto de su división por f (X)). Si denotamos α ∈ K a la clase de equivalencia de X, es decir α ≡ X (mod f (X)), podemos identificar el elemento a0 + a1 X + · · · + am–1 Xm–1 con a0 + a1 α + · · · + am–1 αm–1 y K con el conjunto de estas expresiones. Nótese que αm + fm–1 αm–1 + · · · + f1 α + f0 ≡ 0K y por tanto α puede considerarse como una raíz del polinomio f (X) en K. Se tiene,

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

11

. Teorema 1.9. El conjunto K con las operaciones suma y producto en Fp [α] inducidas por la suma y producto de polinomios en Fp [X] es un

cuerpo con q elementos.

Demostración: El razonamiento es totalmente análogo al de la proposición 1.3 y los detalles se dejan como ejercicio. En particular el inverso de un elemento no nulo se obtiene utilizando el algoritmo de Euclides extendido para polinomios. Nota Se ha señalado que α puede considerarse como raíz de f (X). Dado que este polinomio de grado m tiene m raíces puede plantearse cuál de ellas es α. Sin embargo, a diferencia de lo que sucede con las raíces de un polinomio con coeficientes racionales, las cuales pueden individualizarse y tienen un valor concreto (real o complejo), esto no ocurre en cuerpos finitos. El elemento α puede considerarse como un símbolo, que se toma como raíz de f (X); una vez fijada esta raíz, las restantes pueden expresarse en función de α (ver el ejemplo siguiente).

Ejemplo 1.4. Consideremos el polinomio irreducible X3 + X + 1 ∈ F2 [X], y sea α una raíz. Las otras dos raíces son entonces α2 y α2 + α. Un cuerpo con 8 elementos estaría formado por los elementos:

F8 = {0,1,α,1 + α,α2 ,1 + α2 ,α + α2 ,1 + α + α2 }

(2)

con las siguientes tablas de adición y multiplicación:

+

0

0

1

0

1

α α

1+α

α2

1 + α2

α + α2

1 + α + α2

1+α

α2

α2

α2

1 + α + α2

1+

α2

1

1

0

1+α

α

1+

α

α

1+α

0

1

α + α2

1 + α + α2

α2

1 + α2 α2

0

1

α

1+α

1 + α2

1 + α2

α2

1 + α + α2

α + α2

1

0

1+α

α

α + α2

α + α2

1 + α + α2

α2

1 + α2

α

1+α

0

1

1 + α + α2

1 + α + α2

α + α2

1 + α2

α2

1+α

α

1

0

·

1

α

1+α

α2

1 + α2

α + α2

1 + α + α2

1

α

1+α

α2

1 + α2

α + α2

1 + α + α2

α

α2

α+

α2

1+

α2

1 α

1+

1+α+

1+α

1

1+α+

α2

1

1 + α2

1+α

α2

α2

1+α

1 + α + α2

α + α2

α

1 + α2

1

1 + α2

1 + α2

1

α2

α

1 + α + α2

1+α

α + α2

α + α2

α + α2

1 + α + α2

1

1 + α2

1+α

α

α2

α2

α2

1+α

1+α+

1+α+

α2

1+

α2

α

1+α+

α2

α2

1+α

α2

α+

α2

α+

1+

α2

α2

α2

α+

α2

α + α2

1+α

α2

1+α+

1+α+

α2

α2

α2

0

α+

1+α

α

1

α2

α2

1

α+

Nota El ejemplo anterior construye un cuerpo con 8 elementos utilizando el polinomio irreducible X3 + X + 1 ∈ F2 [X]. Pero una construcción análoga podría obtenerse a partir de una raíz β del polinomio X3 + X2 + 1 ∈ F2 [X] el cual es también irreducible (en realidad, salvo para p = m = 2 en que el único polinomio irreducible es el X2 + X + 1, siempre existe

α

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

12

más de un polinomio irreducible de grado m). En esta otra construcción se obtendrían tablas aditivas y multiplicativas aparentemente diferentes. Sin embargo, el teorema 1.8 garantiza que solo existe un cuerpo con 8 elementos. ¿Cuál es la explicación de esta aparente contradicción? En realidad es un simple problema de etiquetado de los elementos: en concreto, puede comprobarse que la asignación α → β′ = 1 + β se extiende a un isomorfismo entre ambos cuerpos (las tablas para α y β′ son iguales).

1.2. Estructura aditiva y multiplicativa de un cuerpo finito El cuerpo finito Fq contiene dos grupos abelianos, (Fq ,+) y (F∗q ,·). La estructura de estos grupos es particularmente simple. . Teorema 1.10 (Estructura aditiva). Si q = pm , el grupo aditivo (Fq ,+) es un producto directo de m grupos cíclicos de orden p:

(Fq ,+) ≃ Z/pZ × · · · × Z/pZ.

(3)

Demostración: Como se ha indicado (Fq ,+) es un espacio vectorial sobre su subcuerpo primo Fp . Cualquier base de este espacio (por ejemplo, una base del tipo {1,α · · · ,αm–1 } utilizada en el teorema 1.9 induce el isomorfismo indicado.

1.2.1. Representación aditiva En virtud del teorema 1.10 los elementos de Fq pueden representarse como vectores m-dimensionales con coeficientes en Fp , es decir, expresiones de la forma (a1 ,a2 , . . . ,am ) con ai ∈ {0,1, . . . ,p–1}. Así, por ejemplo, los elementos de F8 pueden identificarse con el conjunto de triples binarias {(i,j,k)}|i,j,k ∈ {0,1},

lo que proporciona una forma adecuada de transmitir los elementos de tal cuerpo a través de un canal binario. En esta forma aditiva los elementos pueden sumarse (sumando coordenada a coordenada módulo p) o multiplicarse escalarmente por un elemento de Fp . Para estudiar la estructura multiplicativa, recordemos que, dado un grupo abeliano finito (G,·), llamamos orden de x ∈ G al orden del subgrupo engendrado por x, es decir, ord(x) = min{n | xn = 1} y exponente de G a exp(G) = mcm{ord(x) |x ∈ G}. . Lema 1.11. Si (G,·) es un grupo abeliano finito de exponente n, entonces existe un elemento x ∈ G de orden n.

CC-BY-NC-ND • PID_00200953

13

Demostración: Sea n = pe11 · · · pemm la descomposición de n en factores primos. Como pei i aparece en la factorización, existe xi ∈ G de orden ki pei i para un cierto entero natural ki . Entonces el elemento xki i tendrá orden pei i y por tanto x=

Qm

i=1

xki i tendrá orden exactamente n.

. Teorema 1.12 (Estructura multiplicativa). El grupo multiplicativo (F∗q ,·) es cíclico de orden q – 1.

Demostración: Sea n el exponente de F∗q . En virtud del lema anterior debe existir un elemento de orden n. Por tanto n ≤ q – 1 = #F∗q . Por otra parte, por ser n múltiplo del orden de todo elemento, los q – 1 elementos de F∗q satisfacen la ecuación Xn – 1 = 0, con lo que q – 1 ≤ n y finalmente n = q – 1. Dado que existe un elemento de orden q – 1 el grupo es cíclico. . Definición 1.13 (Elemento primitivo). Llamaremos elemento primitivo de Fq a un generador del grupo cíclico (F∗q ,·).

Nota La noción de elemento primitivo en el contexto de un grupo cíclico finito de orden n y la notación ϕ (n) para el número de tales elementos primitivos puede encontrarse en el módulo 5 del curso Criptografía de la UOC. Tal número es importante en matemáticas y será utilizado en otras partes de este curso, por lo que damos a continuación su definición y algunas de sus propiedades.

. Definición 1.14 (Función de Euler). Para todo número natural n se denota ϕ (n) al número de elementos a; 0 < a < n tales que mcd(a,n) = 1. La función así obtenida se denomina función de Euler.

. Proposición 1.15. La función de Euler verifica las siguientes propiedades: 1) Si p es un número primo, ϕ (p) = p – 1. 2) Si p es un número primo y r un número natural, ϕ (pr ) = pr – pr–1 = pr–1 (p – 1). 3) Si m,n son números naturales primos entre sí (es decir, mcd(m,n) = 1), ϕ (mn) = ϕ (m)ϕ (n)

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

14

La demostración es sencilla y se deja como un ejercicio. . Corolario 1.16. Sea n = pr11 . . . prss la factorización prima del número natural n. Se tiene:

ϕ (n) = n ·

Y

(1 – 1/pi )

(4)

i

El corolario 1.16 muestra que el cálculo de ϕ (n) es fácil si se conoce la factorización de n. Por contra, sin conocer tal factorización, este cálculo es un problema computacionalmente dificil.

1.2.2. Representación multiplicativa En virtud del teorema 1.12, si α es un elemento primitivo de Fq , entonces F∗q = {αi | i = 1, . . . ,q – 1}. Esta representación será fundamental en los sistemas

criptográficos basados en el problema del logaritmo discreto.

Ejemplo 1.5 . Para q = 11, α = 2 es un elemento primitivo de F∗11 .

Ejemplo 1.6 . Como en el ejemplo 1.4, consideremos el polinomio irreducible X3 + X + 1 ∈ F2 [X], y sea α una raíz. Para saber si α es un elemento primitivo, en F8 deberíamos calcular su orden y ver si es máximo. O sea, si el menor entero positivo r tal que αr = 1 es r = q – 1 = 7. Sabemos que α3 + α + 1 = 0, o sea α3 = α + 1. Luego, α4 = α2 + α; α5 = α3 + α2 = α2 + α + 1; α6 = (α3 )2 = α2 + 1 y α7 = α3 + α = 1.

Observación No se conoce ningún algoritmo eficiente para el cálculo de un elemento primitivo, ni siquiera en el caso de los cuerpos Fp , p primo.

Luego α es un elemento primitivo y la tabla de equivalencias entre la representación vectorial (o polinomial) y exponencial es:

Exponencial

Vectorial

Polinomial

0

(0,0,0)

0

α0

(1,0,0)

1

α1

(0,1,0)

α

α2

(0,0,1)

α2

α3

(1,1,0)

1+α

α4

(0,1,1)

α + α2

α5

(1,1,1)

1 + α + α2

α6

(1,0,1)

1 + α2

Observación Observar que al escribir un polinomio como vector, utilizando los coeficientes de su expresión aditiva, hemos empezado por el término de grado cero como primera coordenada.

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

15

2. Bases de cuerpos finitos .

Como se ha indicado, los elementos de Fq , q = pm pueden expresarse como combinación lineal, con coeficientes en Fp , de los elementos de una base. Desde un punto de vista computacional, dos tipos de bases son especialmente importantes. . Definición 2.1 (Base polinómica). Se denomina base polinómica del cuerpo Fq a una base del tipo {1,α · · · ,αm–1 }, con α raíz de un polinomio mónico e irreducible con coeficientes en Fp .

El número de bases polinómicas de Fq será pues igual al número de polinomios mónicos e irreducibles de grado m con coeficientes en Fp . Tal número puede determinarse explícitamente. . Proposición 2.2. Xq – X es el producto de todos los polinomios irreducibles sobre Fp cuyo grado divide a m.

Demostración: Sea g(X) ∈ Fp [X] un polinomio mónico e irreducible de grado d|m. Es decir m = dd′ . En virtud del teorema 1.9 las raíces de g(X) determinan un cuerpo con Fpd elementos y por tanto, por el teorema 1.8, son raíces d

d

′

′

de Xp – X, luego g(X) divide a Xp – X. Se tiene pm – 1 = (pd – 1)(pd(d –1) + pd(d –2) + · · · pd + 1) es decir pd – 1 divide a pm – 1. Un razonamiento análogo con X en d

lugar de p, muestra que Xp

–1

m

– 1 divide a Xp

–1

d

– 1 luego Xp – X y por tanto

g(X) divide a Xq – X. Recíprocamente, un razonamiento similar prueba que si g(X) es un polinomio mónico e irreducible que divide a Xq – X, su grado es un divisor de m. . Corolario 2.3. Si denotamos por Np (d) el número de polinomios irreducibles de grado d sobre Fp , se tiene,

q=

X d|m

dNp (d).

(5)

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

16

El número buscado Np (m) figura como sumando en la expresión anterior. Veamos cómo despejarlo. . Definición 2.4 (Función de Moebius). Llamaremos función de Moebius a la función de variable natural, µ : N –→ {–1,0,1} definida del modo siguiente: si n ∈ N y n = primos, entonces

µ(n) =

8 > > > 1 > > >
> > > > > :

(6)

si ei ≥ 2 para algún valor de i;

(–1)s

si ei = 1 para todo valor de i.

. Lema 2.5. Si n ∈ N, se verifica que

X

µ(d) =

8 > > < 1 > > : 0

d|n

si n = 1;

(7)

si n > 1.

Demostración: El caso n = 1 es trivial. Supongamos pues que n > 1 y sean p1 ,p2 , . . . ,ps los divisores primos distintos de n. Teniendo en cuenta la definición de la función de Moebius,

X

µ(d)

=

µ(1) +

s X

µ(pi ) +

i=1

d|n

0

=

=

1

X

µ(pi pj ) + · · · + µ(p1 p2 . . . ps )

1≤i 0 entonces b := b2 (mod m). Final Desde El resultado es an = b (mod m).

Ejemplo 3.3. Sean a = 3, m = 5, n = 67. Teniendo en cuenta que en base 2, 67 = 1000011, ejecutando las etapas del algoritmo anterior se obtiene 367 ≡ 2 (mod 5).

Notas 1) El algoritmo puede adaptarse a la expresión del exponente n en otra base diferente de 2 (por ejemplo, para base 3 se tendría un algoritmo donde en lugar de elevar al cuadrado se elevaría al cubo). 2) La reducción módulo m puede sustituirse por operación en un cuerpo finito Fq . En particular para m = p primo la reducción módulo p es la operación en el cuerpo primo Fp .

* A su vez necesarios en el sistema criptográfico RSA; consultar la obra de Koblitz (1994).

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

23

La exponenciación puede simplificarse, especialmente en el caso de cuerpos binarios, utilizando bases normales. En efecto se tiene: . Lema 3.3. Sean {a0 ,a1 , . . . ,am–1 } las coordenadas de un elemento a ∈ Fq m–1

en la base normal {α,αp , . . . ,αp

}. El elemento ap tiene por coordena-

das (am–1 ,a0 ,a1 , . . . ,am–2 ).

Demostración: Se tiene (teniendo en cuenta que todos los demás miembros del desarrollo de (a + b)q son potencia de p y por tanto nulos en característica n

p

p, que ai = ai y que αp = αq = α) que: m–1

(a0 α+a1 αp +· · ·+am–1 αp

2

m

m–1

)p = a0 αp +a1 αp +· · ·+am–1 αp = am–1 α+a0 αp +· · ·+am–2 αp

El lema anterior muestra que la elevación a la potencia p implica simplemente una permutación circular de los coeficientes y por tanto, su coste computacional es despreciable. Si p = 2 es la elevación al cuadrado, pieza fundamental en el algoritmo 3.2, la que tiene coste cero.

3.2. Complejidad de la aritmética en cuerpos finitos Veamos cómo obtener una estimación del coste de los algoritmos aritméticos descritos en un cuerpo finito Fq . La disciplina que estudia el coste de los algoritmos y problemas matemáticos se denomina teoría de la complejidad computacional. Si se desea medir la cantidad de computación necesaria para ejecutar un algoritmo, habrá que tener una unidad de medida. Dado que un computador reduce cualquier cálculo a sumas binarias elementales, puede tomarse tal suma como unidad. . Definición 3.4 (Operación bit). Se denomina operación bit a la adición de dos elementos en el cuerpo F2 , es decir, a la suma binaria (módulo 2) de dos números iguales a 0 ó 1 (bits).

Para medir en operaciones bit el tiempo o cantidad de computación de un algoritmo, la teoría de la complejidad computacional introduce dos precisiones: 1) El tiempo debe ser función de la longitud de los datos (inputs). Tales datos son siempre números naturales (o reducibles a ellos: por ejemplo, un elemento de un cuerpo finito con cardinal q = pm queda determinado por m números naturales menores que p).

CC-BY-NC-ND • PID_00200953

24

Cuerpos finitos

2) El tiempo de ejecución de un algoritmo, para una longitud dada de los datos, variará en cada caso concreto. Se adopta el criterio del caso peor tomando una cota válida para toda instancia particular de dicha longitud. . Definición 3.5 (Longitud binaria de un número). Se denomina longitud (binaria) k de un número natural n , al número de dígitos de su expresión en base 2. Dicha longitud es el número natural k tal que 2k–1 ≤ n < 2k y por tanto k = ⌊log2 n⌋ + 1. Nótese que la longitud de un número es también el número de bits de memoria necesarios para almacenarlo en un computador.

. Definición 3.6 (Notación O). Dadas f ,g funciones en las variables naturales k1 ,k2 , . . . ,ks y con valores reales positivos, se dice que f es del orden de g (f = O(g)), si existen constantes reales t,C tales que si ki > t para todo i , f (k1 ,k2 , . . . ,ks ) < Cg(k1 ,k2 , . . . ,ks ).

. Definición 3.7 (Complejidad Polinómica). Un algoritmo con datos iniciales: los enteros n1 ,n2 , . . . ,ns , de longitudes k1 ,k2 , . . . ,ks , se llama de complejidad polinómica si existe un polinomio P en s variables tal que el tiempo de ejecución de dicho algoritmo, medido en operaciones bit, es O(P(k1 ,k2 , . . . ,ks )).

Como veremos, las operaciones aritméticas usuales en cuerpos finitos, en par-

Algoritmos eficientes

ticular las implicadas en los algoritmos criptográficos, tienen una complejidad polinómica. Dado que las operaciones en cuerpos finitos se remiten a operaciones con números enteros, veamos previamente la complejidad de algunos algoritmos básicos con enteros. . Proposición 3.8. •

El tiempo necesario para sumar dos números naturales de longitud binaria k es O(k). La adición de números naturales tiene pues complejidad lineal en la longitud de los datos.

•

El tiempo necesario para multiplicar dos enteros naturales de longitudes k, l , l ≤ k es O(k2 ). La multiplicación tiene pues una complejidad cuadrática en la longitud de los datos.

Los algoritmos de complejidad polinómica se denominan computacionalmente eficientes o buenos, ya que el computador puede ejecutarlos en un tiempo razonable, por oposición a los algoritmos cuya complejidad es exponencial en la longitud de los datos.

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

25

Demostración:

Observación

1) Puede siempre suponerse la misma longitud para ambos sumandos, añadiendo eventualmente ceros a la izquierda de la representación binaria del de menor longitud. La suma se obtiene entonces realizando k sumas binarias, es decir, por definición, k operaciones bit. 2) Sea l ≤ k. Con la regla habitual de multiplicación: colocar el número menor debajo del mayor y multiplicar cada dígito de aquel por este, colocar los resultados en filas desplazadas cada una de ellas una posición a la izquierda respecto de la anterior y sumando, a lo sumo, las l filas, de longitud k + l, (teniendo en cuenta los k–l desplazamientos), se tiene un número de operaciones bit,

O(l(k + l)) = O(2kl) = O(2k2 ) = O(k2 )

Nota La operación de substracción o resta tiene obviamente el mismo tiempo de ejecución que la suma. La división, con la regla habitual, se reduce a multiplicaciones y diferencias y tiene pues igual tipo de complejidad que la multiplicación, es decir, cuadrática. Sin embargo, debe recordarse que la estimación de la complejidad, dada por la notación O, implica una constante, por lo que dos algoritmos con igual complejidad pueden tener de hecho costes muy diferentes. Es el caso de la división, bastante más costosa que la multiplicación. Ello justifica el tratar de evitar o limitar al máximo el número de divisiones; en el caso de la criptografía con curvas elípticas, ello puede conseguirse mediante el uso de coordenadas proyectivas.

Veamos la complejidad del algoritmo 1.4 (de Euclides extendido) necesario, como hemos visto, para el cálculo de inversos en Fp . Obsérvese que en el algoritmo 1.4 los restos ai , obtenidos al iterar el paso 2, forman una sucesión decreciente. Por tanto, el algoritmo finaliza necesariamente en un número finito de etapas. Más concretamente se tiene, . Lema 3.9. Si a ≥ b, el número de etapas necesarias en la ejecución del algoritmo de Euclides extendido es O(log(a)).

Demostración: Basta probar que los restos ai verifican la relación ai+2 < 21 ai , lo que implica que el número de etapas es, a lo sumo, 2⌊log(a)⌋. Ahora bien, si ai+1 ≤

1 2 ai ,

entonces ai+2 < ai+1 ≤

1 2 ai .

Si ai+1 >

1 2 ai ,

la división euclídea

proporciona ai = 1ai+1 + ai+2 , con lo que también en este caso, ai+2 = ai – ai+1 < 1 2 ai .

Debe señalarse que el algoritmo habitual de multiplicación no es el mejor algoritmo conocido para realizar esta operación. Existe otro, debido a Schönhage y Strassen, con complejidad O(k log(k) log log(k))

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

26

. Proposición 3.10. El coste computacional del algoritmo de Euclides extendido es O(log2 a) (es decir, cuadrático en la longitud de los datos).

Demostración: Cada etapa del algoritmo comporta una división (de ai entre ai+1 ), dos multiplicaciones (de qi+1 por xi+1 y por yi+1 ) y dos diferencias (para obtener xi+2 e yi+2 ). El coste total de estas operaciones elementales es O(log2 a). La proposición se deduce teniendo en cuenta el lema anterior. Veamos finalmente la complejidad del algoritmo 3.2, de multiplicar y elevar al cuadrado: . Proposición 3.11. El algoritmo de multiplicar y elevar al cuadrado para calcular an (mod m), tiene una complejidad de O(log2 (m) log(n)).

Demostración: El algoritmo comporta, como máximo, O(log(n)) cuadrados, O(log(n)) multiplicaciones y O(log(n)) divisiones (para realizar las reducciones módulo m), de números, todos ellos de longitud O(log m). Luego la complejidad sería del orden de 3· log(n)· log2 (m), o sea O(log2 (m)· log(n)).

Coste computacional de las operaciones en cuerpos finitos Una vez establecido el coste computacional, medido en operaciones bit, de las operaciones aritméticas elementales con números naturales, así como del algoritmo de Euclides y el algoritmo de multiplicar y elevar al cuadrado, podemos deducir el coste de la aritmética en el cuerpo finito Fq , q = pm , . Proposición 3.12. El coste computacional de una adición (o de una substracción) de elementos de Fq es O(log(q)) operaciones bit.

Demostración: La adición de dos elementos a,b, realizada como adición (o sustracción) de vectores con coeficientes en Fp implica la realización de m adiciones (o sustracciones) de números naturales menores que p y la reducción de cada resultado módulo p. Obsérvese que para tal reducción no es necesaria una división: dado que los números obtenidos son menores o iguales que 2(p – 1), para obtener el resultado módulo p basta dejar el resultado inalterado si el número es menor que p y restarle p caso contrario. Luego la complejidad será, O(m)O(log(p)) = O(m log(p)) = O(log(q)).

(15)

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

27

. Proposición 3.13. El coste computacional (utilizando la representación polinómica) de una multiplicación (o de una división) de elemen3

tos de Fq es O(log q) operaciones bit.

Demostración: Los elementos a ∈ Fq se manejarán como expresiones a = a0 + a1 α + · · · + am–1 αm–1 , ai ∈ {0,1, . . . ,p – 1}. Realizar la multiplicación de a por b implica realizar el producto de los polinomios que los representan y la reducción del resultado módulo f (X).

Observación A efectos computacionales el coste de las sumas o diferencias en un algoritmo en cuerpos finitos suelen considerarse irrelevantes, ya que su complejidad es menor que la de la multiplicación. A veces tal complejidad se expresa no en operaciones bit sino en número de operaciones elementales: en este caso se entienden por tal las multiplicaciones.

La multiplicación de dos polinomios de grado m – 1 sobre Fp implica la realización de O(m2 ) multiplicaciones de enteros módulo p, cada una de las cuales requiere O(log2 p) operaciones bit, más una serie de adiciones que, por tener un coste computacional inferior, podemos no tomar en consideración. Así pues, esta primera etapa requiere O(m2 log2 p) operaciones bit. La división del resultado por el polinomio f (X) requiere realizar O(m) divisiones de enteros módulo p (que realizadas con el algoritmo de Euclides requieren O(log3 p) operaciones bit) y O(m2 ) multiplicaciones de enteros módulo p; por tanto, esta reducción representa un coste de O(m log3 p + m2 log2 p). En total, la multiplicación de a por b implica pues

O(m2 log2 (p) + m log3 (p) + m2 log2 (p)) = O((m log(p))3 ) = O(log3 (q))

(16)

operaciones bit. Por lo que respecta a la división x/y, solo resta probar que el inverso de y ∈ F∗q

Observación

3

puede computarse en O(log q) operaciones bit. Basta aplicar el algoritmo de Euclides a f (X) y al polinomio que representa b, lo que requiere O(m) divisiones de polinomios de grado a lo sumo m, cada una de las cuales comporta O(m log3 p + m2 log2 p) operaciones bit. En definitiva, el coste total es O(m3 log3 p) = O(log3 q) operaciones bit.

3.3. Algoritmos aritméticos en cuerpos finitos El subapartado 3.1 describe los aspectos matemáticos de las operaciones aritméticas en cuerpos finitos. Desde un punto de vista computacional, especialmente para cuerpos de cardinal q muy grande es crucial poder implementar, tanto en software como en hardware, tales operaciones lo más eficientemente posible. Existen numerosos algoritmos con este propósito, adaptados tanto al tipo de cuerpo finito como a la plataforma particular en la que se quiere implementar tal aritmética (por ejemplo, existen algoritmos específicos para plataformas con reducida capacidad de computación y de memoria, como las

Puede observarse que la complejidad de la multiplicación (o división) en un cuerpo finito es cúbica mientras que la multiplicación (o división) en números naturales es cuadrática. Ello obedece al sobrecoste de la reducción módulo p y del cálculo del inverso módulo p.

CC-BY-NC-ND • PID_00200953

28

Cuerpos finitos

tarjetas inteligentes o las etiquetas electrónicas). Es este un activo campo de investigación en la actualidad, pero que desborda los objetivos del curso, por lo que nos limitamos a mostrar un solo ejemplo básico para la adición y la multiplicación en los dos tipos de cuerpos usuales en criptografía: los cuerpos primos Fp y los cuerpos binarios F2m . 1) Cuerpos primos Fp Referencias adicionales

Si el cardinal p del cuerpo es grande, sus elementos tendrán longitud k = ⌈log2 p⌉ mayor que la longitud P de palabra del computador (usualmente P =

16,32 o 64 bits). Si t = ⌈k/P⌉ los elementos a ∈ Fp pueden representarse en la forma A := A[t – 1] . . . A[1]A[0], concatenación de t bloques A[i] de P bits. Para dos tales bloques x,y, notaremos [z,ǫ] si x + y = ǫ2P + z, ǫ = 0,1, 0 ≤ z ≤ 2P – 1. Algoritmo de adición: Sean a,b ∈ {0,1, . . . ,p–1}. El siguiente algoritmo calcula c ≡ a + b (mod p). . Algoritmo 3.14. 1.

Sea (C[0],ǫ) := A[0] + B[0].

2.

Para i = 1, . . . ,t – 1 sea (C[i],ǫ) := A[i] + B[i] + ǫ.

3.

Sea c = C[t – 1] · · · C[0]. Si ǫ = 1 tomar c := c – p. Si c ≥ p tomar c := c – p.

4

c ≡ a + b (mod p).

Ejemplo 3.4. Por simplicidad supondremos P = 2 (como se ha indicado, los valores habituales de P suelen ser 16,32,64, etc). Sea el primo p = 101, lo que implica k = 7, t = 4. Sean a = 83 = 26 + 24 + 2 + 1 (luego A[0] = 11, A[1] = 00, A[2] = 01,A[3] = 01) y b = 71 = 26 + 22 + 2 + 1 (es decir B[0] = 11, B[1] = 01, B[2] = 00,B[3] = 01). Apliquemos el algoritmo anterior a los elementos a,b. Se tiene que (C[0],ǫ) = (10,1) (pues A[0] + B[0] = 3 + 3 = 6 = 1 · 2P + 2). Análogamente se obtiene: (C[1],ǫ) = (10,0), (C[2],ǫ) = (01,0), (C[3],ǫ) = (10,0)

Concatenando los bloques C[i] se tiene: c = 10011010 = 27 + 24 + 23 + 2 = 154. Como este número es mayor que p el resultado final es c := c – p = 53.

Para otros algoritmos de adición y multiplicación, así como de exponenciación y división remitimos a la numerosa bibliografía sobre el tema, por ejemplo, I. Blake; G. Seroussi; N. Smart (2000). Elliptic Curves in Cryptography, London Mathematical Society Lecture Note Series 265. Cambridge: U. Press; y D. Hankerson; A. Menezes; S. Vanstone (2004).Guide to Elliptic Curve Cryptography. Springer.

CC-BY-NC-ND • PID_00200953

29

Algoritmo de multiplicación: Sean a,b ∈ {0,1, . . . ,p – 1}. El producto en Fp implica el cálculo del producto entero c = a · b y la posterior reducción módulo p. Para la etapa de reducción existen diversos algoritmos (Barret, Montgomery, etc). El siguiente algoritmo calcula el producto entero c = a · b. . Algoritmo 3.15. 1.

Sean R0 := 0, R1 := 0, R2 = 0.

2.

Para k = 0,1, . . . 2t – 2, calcular, 2.1: Para cada par (i,j); i + j = k, 0 ≤ i,j ≤ t – 1. UV := A[i] · B[j]. (R0 ,ǫ) := R0 + V. (R1 ,ǫ) := R1 + U + ǫ. R2 := R2 + ǫ. 2.2 C[k] := R0 , R0 := R1 , R1 := R2 , R2 := 0.

3

C[2t – 1] := R0 .

4

c = C[2t – 2] . . . C[0].

Ejemplo 3.5. Sean los mismos datos del ejercicio 3.4. Apliquemos el algoritmo anterior a a,b. Para k = 0 se tiene UV = A[0]B[0] = 9 = 1001 (luego U = 10, V = 01). Por tanto

(R0 ,ǫ) = (01,0), (R1 ,ǫ) = (10,0), R2 = 0

luego c[0] = 01. Análogamente se obtendría,

C[1] = 01, C[2] = 00, C[3] = 00, C[4] = 11, C[5] = 01, C[6] = 01

Es decir c = 011100000101 = 5893.

2) Cuerpos binarios F2m En este caso la longitud binaria del cardinal del cuerpo es obviamente m. En la base polinómica determinada por una raíz α del polinomio irreducible de grado m f (X), los elementos a ∈ F2m se expresan en la forma: a = a0 + a1 α + · · · + am–1 αm–1 , ai = 0,1. Escribimos f (X) = Xm + r(X).

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

30

La adición de dos elementos a,b ∈ F2m es trivial: expresados a,b en cualquier base basta realizar la suma binaria de los dos bits correspondientes a cada una de las m coordenadas. Algoritmo de multiplicación. El producto de los elementos a,b comporta la multiplicación de dos polinomios binarios a(X),b(X), de grado a lo sumo m – 1 y la posterior reducción módulo f (X). El siguiente algoritmo resuelve el primer problema. El resultado c(X) polinomio de grado a lo sumo 2m – 2 puede expresarse como una palabra C formada por t bloques C[j] de tamaño P cuyas componentes son el bloque B representando a b(X) o bien un bloque nulo. . Algoritmo 3.16. 1.

C := concatenación de t bloques de tamaño P con entradas nulas.

2.

Para k = 0,1, . . . P – 1, Para j = 0,1, . . . ,t – 1. Si el bit k de A[j] es 1 colocar B en la posición k del bloque A[j]. Caso contrario colocar un bloque nulo en dicha posición.

3.

C es la representación de c(X).

Ejemplo 3.6. Sean a = 101101 y P = 2, luego t = 3, A[0] = 01, A[1] = 11, A[2] = 10. C estará formado por 3 bloques de tamaño 2 cuyas entradas son nulas o B: Para cada k = 0,1 si el bit correspondiente de A[j]; j = 0,1,2 es 1 se pone B en la casilla correspondiente de C[j] y caso contrario un bloque 0. Queda finalmente C = [B,0][B,B][0,B]. Nótese que el resultado corresponde a la forma polinómica c(X) = BX5 + BX3 + BX2 + B, el mismo resultado que se habría obtenido multiplicando a(X) = X5 + X3 + X2 + 1 por B.

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

31

Ejercicios de autoevaluación 1. Justificar la necesidad de que n sea primo para que Zn , el conjunto de los enteros módulo n, tenga estructura de cuerpo. Mostrar que Z6 no es un cuerpo. 2. Construir explícitamente el cuerpo finito F9 con 9 elementos y dar la tabla de equivalencias vectorial-exponencial. 3. ¿Qué elementos de F9 se pueden tomar como generadores de su grupo multiplicativo? ¿Qué elementos de F9 tienen raíz cuadrada en este cuerpo? 4. ¿Para qué valores de p, (p = 3,5,7,11,13,19,23), se puede construir un cuerpo de orden p2 usando el polinomio x2 + 1? 5. Encontrar los valores de m para los cuales X2 + mX + 2 es un polinomio irreducible y primitivo en Z11 [X]. 6. Sea q = pm , p primo, r ∈ N. Probar que el cuerpo Fpr está contenido en el cuerpo Fq si, y solamente si, r es un divisor de m. 7. Sea el cuerpo F8 , definido por el polinomio binario f (X) = X3 + X + 1 y sea α una raíz de f (X). Expresar en la base polinómica {1,α,α2 } los elementos α5 y 1+αα2 . 8. Demostrar que en el cuerpo Fq la suma de todos los elementos es cero y si q es una potencia de un número primo impar, el producto de todos los elementos no nulos es –1. 9. Demostrar que en un cuerpo finito de característica p, a) Si p = 2, cada elemento es un cuadrado; b) Si p es impar, exactamente la mitad de los elementos son cuadrados. 10. Escribir la tabla de equivalencias vectorial-exponencial para el cuerpo finito F24 , con generador α. α7 + α23 +1 a) Determinar δ como potencia de α, donde δ = α10 + 1 + α12 b) Encontrar todas las raíces de la ecuación:

α7 x2 + (α2 + α9 )x +

1+α =0 α4

11. Utilizar el algoritmo extendido de Euclides para calcular: a) El inverso de 43 en el cuerpo Z101 . b) El inverso de (1,2) en el cuerpo F9 (generar F9 a partir del polinomio irreducible f (X) = X2 + 1) 12. Encontrar todas las bases normales del cuerpo F8 , sobre el cuerpo F2 . 13. Sea q = pm , p primo, Fq el cuerpo finito con q elementos y B : {x1 , . . . ,xm } una base de Fq sobre Fp . Dado x ∈ Fq sea la aplicación lineal ϕx : Fq → Fq dada por: ϕx (y) = xy. Como toda aplicación lineal ϕ vendrá determinada en la base B por una matriz m × m con coeficientes en Fp , A = (aij ). P Se denomina Traza de x a Tr(x) = i aii ∈ Fp (es decir, lo que se denomina traza de la matriz A, la suma de los elementos de su diagonal principal) y Norma de x a N(x) = |A| ∈ Fp (determinante de la matriz A). Aunque definido en términos de una base concreta, puede verse en cualquier texto de álgebra lineal que Tr(x),N(x) son los mismos en cualquier base. Al variar x ∈ Fq se tienen dos aplicaciones Tr : Fq → Fp y N : Fq → Fp . Probar las siguientes propiedades: i) Tr(x + y) = Tr(x) + Tr(y), i’) N(x · y) = N(x) · N(y), x,y ∈ Fq , ii) Tr(λx) = λTr(x), ii’) N(λx) = λm N(x), λ ∈ Fp , x ∈ Fq , iii) Tr(λ) = mλ, iii’) N(λ) = λm , λ ∈ Fp .

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

32

14. a) Multiplicar en binario los números a = 103, b = 65. Determinar el número de operaciones bits realizadas. b) Generalizar al caso a número de longitud binaria k y b = 2k–1 + 1. c) Comparar el número de operaciones bits de esta última multiplicación con la complejidad general para la multiplicación obtenida en la proposición 3.8. 15. a) Formular un algoritmo para la exponenciación an en un cuerpo finito análogo al algoritmo 3.2 para la exponenciación modular en Z. b) Determinar la complejidad del algoritmo anterior. c) Aplicar al caso del cuerpo F8 , a = 1 + α, α raíz del polinomio X3 + X + 1 ∈ F2 [X] y n = 5.

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

33

Soluciones 1) Si n no fuese primo admitiría una factorización n = ab, 1 < a,b < n. Los elementos a,b no admiten entonces inverso: si por ejemplo a admitiese inverso a–1 , a–1 ∈ {1,2, . . . ,n – 1} se tendría que aa–1 = 1 y multiplicando ambos miembros por b: (ba)a–1 = na–1 y 1b = b. Dado que n · a–1 = 0 en Zn , entonces b = 0, lo que es una contradicción. En el caso n = 6, de lo anterior se deduce que los elementos 2 y 3 no admiten inverso, lo que también puede comprobarse directamente, viendo que el producto de 2 o de 3 por los elementos del conjunto {1,2,3,4,5} nunca es 1. 2) De acuerdo a la construcción dada por el teorema 1.9 es necesario tomar un polinomio irreducible de grado dos sobre el cuerpo primo con tres elementos F3 . Un tal polinomio es por ejemplo el X2 + 1. Si α es una raíz de dicho polinomio se tendría:

F9 = {0,1,2,α,2α,1 + α,2 + α,1 + 2α,2 + 2α} Las tablas aditivas y multiplicativas para este cuerpo podrían construirse como en el ejemplo 1.4. Sin embargo, el polinomio usado no es primitivo y una raíz de este polinomio no nos sirve como generador del grupo multiplicativo del cuerpo (observemos que α4 = 1). Tomemos ahora el polinomio X2 + 2X + 2 y sea α una raíz y por tanto, α2 = 1 + α. Se tiene la correspondencia. Exponencial

Vectorial

Polinomial

0

(0,0)

0

α0

(1,0)

1

α1

(0,1)

α

α2

(1,1)

1+α

α3

(1,2)

1 + 2α

α4

(2,0

2

α5

(0,2)

2α

α6

(2,2)

2 + 2α

α7

(2,1)

2+α

3) Puesto que F∗9 es un grupo cíclico de orden 8, la teoría general de grupos cíclicos nos dice que existen φ (8) = φ (23 ) = 22 · 1 = 4 generadores del grupo multiplicativo de este cuerpo. Si α es un tal generador (por ejemplo, como en el ejercicio anterior, puede tomarse como α una raíz del polinomio X2 + 2X + 2 ∈ F3 [X]) se tiene: F∗9 = {α,α2 ,α3 ,α4 ,α5 ,α6 ,α7 ,α8 = 1} Los generadores serán de la forma αi , donde mcd(i,8) = 1 y, por lo tanto, i = 1,3,5 y 7. Así pues, los generadores serán {α,α3 ,α5 ,α7 }. En efecto, todos estos elementos tienen orden 8 y por tanto, sus potencias recorren todo F∗9 . Los elementos que tienen raíz cuadrada son aquellos en los que el exponente es par, o sea {α2 ,α4 ,α6 ,α8 }. En efecto estos elementos tienen raíz cuadrada, de hecho, cada uno de ellos tiene dos raíces cuadradas: por ejemplo α2 tiene por raíz α pero también α5 ((α5 )2 = α10 = α2 ). En cambio los elementos con exponente i impar no admiten raíz cuadrada, lo que puede comprobarse directamente. Obsérvese que si β ∈ F9 fuese una raíz cuadrada de αi , es decir β2 = αi , puesto que αi tiene orden 8, β tendría orden 16, lo que es absurdo pues su orden debe ser divisor del orden del grupo, que es 8. 4) Debemos averiguar para qué valores de p se puede construir un cuerpo con p2 elementos a partir del polinomio irreducible X2 + 1, es decir, debemos poder construir un cuerpo Fp2 = Zp [X]/(X2 + 1). Si f (X) = X2 + 1 no fuera irreducible, podría ser descompuesto de la forma (X – a)(X – b). Entonces, si existen valores X = a o X = b tales que f (X) = 0 (mod p), f (X) no sería irreducible, y por lo tanto, Zp [X]/X2 + 1 no será un cuerpo. Supongamos f (X) = 0, entonces sería X2 + 1 = 0 (mod p) y X2 = –1 = p – 1 (mod p). Así pues, comprobaremos si p – 1 tiene raíz cuadrada módulo p y, en caso afirmativo, f (X) no será irreducible. a) Para p = 3: x2 = 2 no tiene solución, por tanto f (X) es irreducible. b) Para p = 5: x2 = 4 tiene solución x = 2, x = –2, por tanto f (X) no es irreducible.

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

34

c) Para p = 7: x2 = 6 no tiene solución, por tanto f (X) es irreducible. d) Para p = 11: x2 = 10 no tiene solución, por tanto f (X) es irreducible. e) Para p = 13: x2 = 12 tiene solución x = 5 (52 = 25 = 12 (mod p)), por tanto f (X) no es irreducible. f) Para p = 19: x2 = 18 no tiene solución, por tanto f (X) es irreducible. g) Para p = 23: x2 = 22 no tiene solución, por tanto fXx) es irreducible. Los valores de p que cumplen que Fp2 = Zp [X]/X2 + 1 es un cuerpo son: 3,7,11,19 y 23. Obsérvese que son todos los primos del conjunto dado congruentes con 3 módulo 4. 5) Debemos encontrar todos los valores de m tales que el polinomio p(X) = X2 + mX + 2 sea irreducible y primitivo en Z11 [X]. Primero encontraremos los valores de m para los cuales p(X) es irreducible. Para ello, supondremos que p(X) se puede descomponer en factores, X2 + mX + 2 = (X – a)(X – b) = X2 – bx – ax + ab = X2 – (a + b)X + ab. O sea, –(a + b) = m y ab = 2. Las posibles soluciones son: (a = 1,b = 2,m = 8); (a = 2,b = 1,m = 8), (a = 3,b = 8,m = 0), (a = 4,b = 6,m = 1), (a = 5,b = 7,m = 10), (a = 6,b = 4,m = 1), (a = 7,b = 5,m = 10), (a = 8,b = 3,m = 0), (a = 9,b = 10,m = 3), (a = 10,b = 9,m = 3). La conclusión es que los posibles valores de m para que p(x) sea irreducible son 2,4,5,6,7 y 9. Finalmente, debemos sustituir m por estos valores y ver si p(x) es primitivo. Para ver que un polinomio es primitivo, debemos comprobar que sus raíces tengan orden pn – 1, o sea, orden 120 en nuestro caso. Un elemento α tiene orden i si αi = α0 = 1 en el cuerpo en el que estamos trabajando. Entonces, podemos tomar α = [X] como raíz e ir calculando las potencias de este elemento hasta llegar a un exponente i tal que αi = 1. Si i = 120 (orden máximo), podemos decir que α es primitivo y el polinomio correspondiente también (no hace falta calcular todas las potencias de α hasta 120, basta calcular αi con i divisor de 120). Finalmente, después de las operaciones pertinentes, nos quedan como valores que hacen que p(x) sea primitivo m = 4,5,6 y 7. r

6) Si r|m se ha probado en la proposición 2.2 que el polinomio Xp – X divide al polinomio m Xp – X. Por tanto las raíces del primero (que constituyen el cuerpo Fpr ) son también raíces del segundo, es decir, elementos del cuerpo Fq . Supongamos recíprocamente que Fpr ⊂ Fpm . Puesto que ambos cuerpos contienen a Fp se tiene la cadena Fp ⊂ Fpr ⊂ Fpm . Entonces se tiene que: • • •

Fpr es un espacio vectorial de dimensión r sobre Fp Fpm es un espacio vectorial de dimensión m sobre Fp Fpm es un espacio vectorial sobre Fpr . Llamemos s a su dimensión.

Pero es fácil demostrar la siguiente relación entre las tres dimensiones:

n = [Fpm : Fp ] = [Fpm : Fpr ][Fpr : Fp ] = rs ⇒ r|m [Basta tomar bases {v1 ,v2 , . . . ,vs } de Fpm sobre Fpr y {w1 ,w2 , . . . ,wr } de Fpr sobre Fp y comprobar que los productos vi wj forman una base de Fpm sobre Fp .] 7) Por ser raíz del polinomio f (X) = X3 + X + 1, α verifica (en binario) α3 = α + 1. Por tanto a) α4 = α2 + α y α5 = α3 + α2 = α + 1 + α2 . b)

α 1+α2

= α(1 + α2 )–1 . Para obtener el inverso de 1 + α2 se aplica el algoritmo de Euclides para a = a0 = X3 + X + 1, b = a1 = X2 + 1 y xo = 1, x1 = 0, y0 = 0, y1 = 1. Se obtiene: a2 = 1, a3 = 0, x2 = 1, y2 = X. Luego

1 = mcd(a,b) = X3 + X + 1 + X(X2 + 1) ⇒ (1 + α2 )–1 = α Finalmente:

α 1+α2

= αα = α2 . m

8) El cuerpo Fpm está formado por todos los elementos que cumplen Xp – x = 0. Sean estos m elementos {0,a1 ,a2 , · · · ,apm –1 }. Entonces Xp –1 – 1 = (X – a1 )(X – a2 ) · · · (X – apm –1 ). Haciendo operaciones:

Xp

m

–1

– 1 = Xp

m

–1

– (a1 + a2 + · · · + apm –1 ) Xpm – 2 + · · · + (–1)p | {z } =0

m

–1

Y

ai

CC-BY-NC-ND • PID_00200953

35

En cualquier caso la suma de todos los elementos de Fpm da cero y, si p es impar, pm – 1 es par y, entonces, el producto es igual a –1. 9) Supongamos que p = 2, entonces podemos escribir el cuerpo finito F2m como F2m = m {0,α1 ,α2 , · · · ,α2 –1 = 1}, donde α es un elemento primitivo. Vamos a ver si α tiene raíz cuadrada:

m

1 = α0 = α2

–1

m

=⇒ α = α2 =⇒

√

m–1

α = α2

Como α tiene raíz cuadrada, todos los elementos de F2m la tendrán también. En segundo lugar, supongamos que p = 2k + 1. En este caso podemos escribir Fpm = {0,α1 ,α2 , m m · · · ,αp –1 }, donde α es un elemento primitivo y αp –1 = α0 . Evidentemente, α2k tiene raíz cuadrada, así como el elemento cero. Por lo tanto, los elementos que podemos asegurar que tienen raíz cuadrada serán:

{0,α0 ,α2 , · · · ,αp

m

–1

}

que son exactamente la mitad de los elementos no nulos de Fpm y, además, el cero. Vamos a ver que no hay más elementos en Fpm con raíz cuadrada y, para ello, consideremos φ : Fpm –→ Fpm , definida como φ (x) = x2 . En esta aplicación, excepto el cero, todas las imágenes tienen exactamente dos antiimágenes. En efecto, supongamos que dos elementos x,y ∈ Fpm ,x 6= y tienen un mismo cuadrado, es decir, x2 = y2 . Entonces x2 = y2 =⇒ x2 – y2 = 0 =⇒ (x + y) · (x – y) = 0 Esta ecuación tiene dos posibles soluciones: x = y y x = –y. Como p es impar, siempre existirán valores diferentes x,y ∈ Fpm tales que x = –y, excepto en el caso del cero. 10) Tomemos el cuerpo finito F24 = Z2 [X]/f (x), dónde f (x) se un polinomio irreducible de grado 4 y coeficientes en Z2 . Nuestro primer problema es, pues, encontrar un polinomio irreducible y primitivo de cuarto grado. Empecemos, primero, con los polinomios irreducibles de grado 1 (hay dos: X,X + 1). Los de grado 2 (hay uno: X2 + X + 1). Los de grado 3 (hay dos: X3 + X2 + 1; X3 + X + 1). Los de grado 4 (hay 3: X4 + X3 + X2 + X + 1; X4 + X3 + 1; X4 + X + 1). De entre estos últimos polinomios de cuarto grado, buscaremos uno que sea primitivo, es decir, que sus raíces tengan orden pn – 1 = 15. Comprobemos el polinomio X4 + X3 + X2 + X + 1: Sea α una raíz, entonces

α4 = α3 + α2 + α + 1, α5 = α4 + α3 + α2 + α = 1,

O sea, α5 = 1 y, por tanto, α no es de orden 15 y el polinomio no es primitivo. Comprobemos ahora el polinomio X4 + X3 + 1: Sea α una raíz, entonces

α4 = α3 + 1 α5 = α4 + α = α3 + α + 1 α6 = α4 + α2 + α = α3 + α2 + α + 1 α7 = α4 + α3 + α3 + α = α2 + α + 1 α8 = α3 + α2 + α α9 = α4 + α3 + α2 = α2 + 1 α10 = α3 + α

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

36

α11 = α4 + α2 = α3 + α2 + 1 α12 = α9 + α6 + α3 + 1 = α + 1 α13 = α2 + α α14 = α3 + α2 α15 = 1

Por tanto, el polinomio X4 + X3 + 1 se primitivo. Así pues, utilizaremos el polinomio primitivo X4 + X3 + 1 y F24 = Z2 [X]/X4 + X3 + 1. La tabla de equivalencias vectorial-potencial es:

•

0

(0000)

α0

(1000)

α1

(0100)

α2

(0010)

α3

(0001)

α4

(1101)

α6

(1111)

α7

(1110)

α8

(0111)

(0101)

α11

(1011)

α12

(1100)

α13

(0110)

(1001)

α5

α9

(1010)

α10

α14

(0011)

Para calcular δ como potencia de α, calcularemos:

δ = α10 +

•

α7 + α23

1+

α12

+ 1 = α10 +

α7 + α8 α

+ 1 = α10 +

α4 α

+ 1 = α10 + α3 + 1 = α12 .

Para encontrar las raíces de la ecuación dada, debemos resolver:

α7 x2 + (α2 + α9 )x +

1+α = 0, α4

o sea: α7 x2 + x + α8 = 0. Por búsqueda exhaustiva, encontramos las raíces α3 y α13 . 11) En primer lugar, el inverso de 43 en Z101 será un x tal que 43 · x = 1 (mod 101). Por lo tanto, 43x = 1 + 101y. Aplicamos el algoritmo extendido de Euclides con a0 = a = 101,a1 = b = 43. Los valores encontrados son: a0 = a = 101,a1 = b = 43,a2 = 15,a3 = 13,a2 = 2,a3 = 0, q1 = 2,q2 = 2,q3 = 1,q4 = 6, x0 = 1,x1 = 0,x2 = 1,x3 = –2,x4 = 3,x5 = –20, y0 = 0,y1 = 1,y2 = 2,y3 = –5,y4 = 7,y5 = –47. Finalmente, 1 = –101·20 + 43·47 y 1 = 43·47 (mod 101). Por tanto, 43–1 = 47 (mod 101). En segundo lugar vamos a calcular el inverso de (1,2) en F32 , donde F32 se ha generado a partir de f (X) = X2 + 1. El vector (1,2), en forma polinómica, está representado por 1+2α, donde α = [X] ∈ Z3 [X]/X2 + 1. Utilizando el algoritmo extendido de Euclides entre X2 + 1 y 2X + 1 obtenemos: a0 = a = X2 + 1,a1 = b = 2X + 1,a2 = 2, q1 = 2X – 1, x0 = 1,x1 = 0,x2 = 1, y0 = 0,y1 = 1,y2 = 2X – 1.

CC-BY-NC-ND • PID_00200953

37

Finalmente, 2 = 1 · (X2 + 1) – (2X – 1) · (2X + 1), o sea: (2X – 1) · (2X + 1) = 1

(mod X2 + 1).

Por lo tanto, (1,2)–1 = (–1,2). 12) Sea α ∈ F8 , raíz del polinomio irreducible X3 +X+1. El conjunto B = {α,α2 ,α4 = 1+ α + α2 } forma una base normal. Por el teorema 2.11 cualquier otra base B′ es de la forma B′ = BC, con C = [c0 ,c1 ,c2 ] matriz circulante no singular, es decir, con determinante no nulo (y por tanto, en este caso determinante igual a 1). El problema se reduce pues a encontrar tales matrices. Puesto que los coeficientes ci ∈ {0,1} existen 8 matrices circulantes. Veamos cuáles son no singulares: a) Sean c0 = c1 = c2 = 0: la matriz es obviamente singular (todos sus coeficientes son nulos). b) Sean c0 = c1 = c2 = 1: la matriz es singular (pues tiene sus tres filas iguales). c) Sean c0 = 1 y c1 = c2 = 0: la matriz obtenida es la identidad, no singular, y se tiene B′ = B. d) Sean c0 = 0, c1 = 1, c2 = 0: la matriz obtenida es

0

0 B B B 0 @ 1

1 0 0

0

1

C C , 1 C A 0

matriz no singular que proporciona la base normal B′ = {α4 ,α,α2 } (Nótese que (α4 )2 = α8 = α. e) Sean c0 = 0, c1 = 0, c2 = 1: la matriz obtenida es

0

0

B B B 1 @ 0

0 0 1

1

1

C C , 0 C A 0

matriz no singular que proporciona la base normal B′ = {α2 ,α4 ,α}. f) Sean c0 = 1, c1 = 1, c2 = 0: la matriz obtenida es

0

1 B B B 0 @ 1

1 1 0

0

1

C C , 1 C A 1

matriz que es singular. g) Sean c0 = 1, c1 = 0, c2 = 1: Se obtiene también una matriz singular. h) Sean c0 = 0, c1 = 1, c2 = 1: De nuevo la matriz obtenida es singular. Como conclusión: existen tres bases normales, las {α,α2 ,α4 }, {α4 ,α,α2 }, y {α2 ,α4 ,α}. Obsérvese, sin embargo, que las dos últimas son simplemente permutaciones de la primera. 13) Si A,B son las matrices asociadas con las aplicaciones ϕx , ϕy ; x,y ∈ Fq se tiene que la matriz asociada con ϕx+y es A + B de donde se deduce i). La matriz asociada con ϕλx es (λaij ), de donde se deduce ii). La matriz asociada con ϕ (λ ) es la matriz diagonal con λ en todos los elementos de la diagonal principal, de donde se deduce iii). Las propiedades i’), ii’) y iii’) se deducen de la misma forma, teniendo en cuenta que la matriz asociada a ϕxy es AB.

Cuerpos finitos

CC-BY-NC-ND • PID_00200953

Cuerpos finitos

38

14) a) La expresión binaria de ambos números es a = 1100111, b = 1000001. Con la regla habitual de multiplicación se obtiene

a+

a

=

0

0

0

0

0

0

1

1

0

0

1

1

1

a′

=

1

1

0

0

1

1

1

0

0

0

0

0

0

=

1

1

0

1

0

0

0

1

0

0

1

1

1

a′

=a·b

Se han realizado un total de 13 operaciones bits (suma de dos números binarios de longitud 13). El resultado obtenido ha sido: 212 + 211 + 29 + 25 + 22 + 2 + 1 = 6695. b) Ambos números tienen longitud binaria k y expresión binaria a = 1ak–1 · · · a1 a0 , b = 10 · · · 01. Dado que b tiene solo dos coeficientes no nulos (el primero y el último), habría que realizar la suma de dos números binarios de longitud 2k–1, obteniéndose un número con longitud, según los casos, 2k – 1 o 2k, por lo que el número de operaciones bits será a lo sumo 2k. c) La complejidad para el producto anterior es pues O(k), lineal en la longitud de los datos. La complejidad en el caso general, Proposición 3.8, era sin embargo O(k2 ). Recuérdese, sin embargo, que el símbolo O daba una expresión “en el caso peor”. 15) a) El algoritmo debe calcular una expresión de la forma an , a ∈ Fq , n ∈ N. La reducción módulo m en el algoritmo 3.2 debe sustituirse ahora por “operaciones” (multiplicaciones y cuadrados) en el cuerpo finito. Con este cambio se obtiene al algoritmo deseado. b) El algoritmo exige realizar, a lo sumo, O(log(n)) multiplicaciones y O(log(n)) cuadrados (a diferencia del Algoritmo 3.2 no son necesarias divisiones). Como la complejidad de una multiplicación y un cuadrado en Fq es O(log2 (q)) el coste total será:

O(log(n))O(log2 (q)) + O(log(n))O(log2 (q)) = O(log(n) log2 (q))

c) En este caso la expresión binaria de n es 5 = 101. Habría pues que realizar tres etapas: • Etapa 1: s2 = 1, luego b := 1 + α y b := (1 + α)2 = 1 + α2 . • Etapa 2: s1 = 0, luego b := (1 + α2 )2 = 1 + α + α2 . • Etapa 3: s0 = 1, luego b := (1 + α)(1 + α + α2 ) = α.

CC-BY-NC-ND • PID_00200953

Bibliografía

Cuerpos finitos

39

.

Koblitz, N. (1994). “A Course in Number Theory and Cryptography, Second Edition”. Nueva York: Springer (Graduate Texts in Mathematics, núm. 114). Lidl, R.; Niederreiter, H. (1997). “Finite Fields”. Encyclopedia of Mathematics and its Applications (vol. 20, núm. 20, pág. 2). Cambridge: Cambridge U. Press. Menezes, A. (1993) (ed.). Applications of Finite Fields. Massachusetts: Kluwer Academic Publishers.