View
73
Download
1
Category
Preview:
DESCRIPTION
Apuntes Universidad Oberta de Cataluña (Máster seguridad informática)
Citation preview
Cuerpos finitosLloren Huguet Rotger
Josep Rif Coma
Juan Gabriel Tena Ayuso
PID_00200953
Los textos e imgenes publicados en esta obra estn sujetos excepto que se indique lo contrario auna licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 Espaa deCreative Commons. Podis copiarlos, distribuirlos y transmitirlos pblicamente siempre que citisel autor y la fuente (FUOC. Fundaci per a la Universitat Oberta de Catalunya), no hagis un usocomercial y no hagis una obra derivada. La licencia completa se puede consultar enhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es
CC-BY-NC-ND PID_00200953 Cuerpos finitos
ndice
Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1. Existencia y propiedades de los cuerpos finitos . . . . . . . . . . . . . . 7
1.1. Existencia y construccin de cuerpos finitos . . . . . . . . . . . . . . . . . . 7
1.2. Estructura aditiva y multiplicativa de un cuerpo finito . . . . . . . . 12
1.2.1. Representacin aditiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2. Representacin multiplicativa . . . . . . . . . . . . . . . . . . . . . . . . 14
2. Bases de cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Computacin en cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1. Aritmtica en cuerpos finitos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1. Multiplicacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2. Divisin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.3. Exponenciacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2. Complejidad de la aritmtica en cuerpos finitos . . . . . . . . . . . . . . 23
3.3. Algoritmos aritmticos en cuerpos finitos . . . . . . . . . . . . . . . . . . . . . 27
Ejercicios de autoevaluacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Bibliografa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
CC-BY-NC-ND PID_00200953 5 Cuerpos finitos
Introduccin
Los sistemas y protocolos criptogrficos que sern objeto de estudio en mdu-
los 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,
multiplicacin y divisin y obviamente, como siempre en criptografa, este
tipo de alfabeto debe ser finito.
Los cuerpos finitos han sido estudiados desde hace siglos por diversos mate-
mticos, en particular Evariste Galois (de hecho son tambin conocidos como
cuerpos de Galois), pero es en los ltimos 50 aos cuando el inters por estas
estructuras ha conocido un crecimiento espectacular, debido a sus aplicacio-
nes en diferentes campos de indudable inters para el mundo industrial y
financiero, como son la criptografa o los cdigos correctores de errores.
La teora de cdigos correctores de errores trata de preservar la calidad de la
informacin cuando es transmitida a travs de canales susceptibles de sufrir
perturbaciones, que introducen errores en el mensaje transmitido. Un cdigo
corrector permite, dentro de ciertos lmites, detectar y corregir tales errores.
Esta teora comparte con la criptografa fines (si los cdigos correctores tratan
de defender la informacin de la degradacin natural la criptografa trata de
defenderla de los ataques humanos) y tcnicas, en particular diversos sistemas
criptogrficos (McEliece, Niederreiter), estn basados en cdigos correctores.
Denotaremos Fq a un cuerpo finito con q elementos (algunos autores utilizan
la notacin GF(q), por Galois field con q elementos). El presente mdulo es-
tudia esta estructura matemtica, con especial nfasis en los aspectos compu-
tacionales de su aritmtica.
CC-BY-NC-ND PID_00200953 6 Cuerpos finitos
Objectivos
En los materiales didcticos de este mdulo el estudiante encontrar los con-
tenidos 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 nmero primo.
2. Saber calcular la tabla de equivalencias polinomial-exponencial y saber cal-
cular en un cuerpo finito Fq dando los resultados en cualquiera de las dos
representaciones.
3. Saber reconocer la complejidad computacional de un clculo en cuerpos
finitos.
4. Conocer y saber aplicar los principales algoritmos aritmticos en cuerpos
finitos.
CC-BY-NC-ND PID_00200953 7 Cuerpos finitos
1. Existencia y propiedades de los cuerpos finitos.
En este apartado se muestra para qu valores de q existe un cuerpo finito Fq y
cmo construirlo explcitamente y se estudian sus propiedades y estructura.
1.1. Existencia y construccin de cuerpos finitos
En primer lugar sealemos el siguiente resultado del teorema 1.
Lectura recomendada
Sobre el teorema de
Wedderburn podis
consultar la obra de Lidl y
Niederreiter (1997).
.
Teorema 1.1 (Teorema de Wedderburn). Todo cuerpo finito es
conmutativo (es decir, su multiplicacin es conmutativa).
Observacin
Existen cuerpos infinitos queno son conmutativos, comoel cuerpo de los cuaterniones.
.
Definicin 1.2 (Caracterstica de un cuerpo). La caracterstica de un
cuerpo K se define como el mnimo 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 nmeros
reales, decimos que K tiene caracterstica 0. Caso contrario p debe ser
un nmero primo (si p = r s, 1 < r,s < p se tendra que 0 = p 1 =
(r 1)(s 1) y uno de los dos factores debera ser cero, en contradiccin
con la minimalidad de p) y el cuerpo se dice de caracterstica prima p.
Un primer ejemplo de cuerpo finito viene dado por el siguiente resultado.
.
Proposicin 1.3. Para todo nmero primo p el conjunto Zp de los en-
teros mdulo p, con la suma y producto inducidos por las de Z, cons-
tituye un cuerpo conmutativo.
Demostracin: Recordemos que el conjunto Zp de los enteros mdulo p es
el conjunto de clases de equivalencia de nmeros enteros, donde dos enteros
x,y son equivalentes si, y solamente si, son congruentes mdulo 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}.
CC-BY-NC-ND PID_00200953 8 Cuerpos finitos
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 (Fp = Fp {0},) la multiplicacin es conmutativa, el elemento 1 acta
como unidad y dado un elemento a Fp la existencia de inverso (y unmtodo
efectivo de calcularlo) se deduce del algoritmo de Euclides (el cual se describir
a continuacin): 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 (ntese que p 0
(mod p)) ax 1 (mod p), luego el elemento x (mod p) es el inverso del a.
Cuerpo binario
Si p = 2, se tiene el cuerpocon dos elementosF2 = {0,1} base de lacomputacin binaria (lasoperaciones de cuerpocoinciden con lasoperaciones lgicasO-exclusivo (XOR) y AND).
El algoritmo de Euclides (Euclides, libro VII), que permite obtener el mximo
comn divisor d de dos nmeros a,b N, es uno de los algoritmos bsi-
cos en matemtica computacional. Una modificacin - algoritmo de Euclides
extendido- permite obtener d como combinacin lineal de a y b con coefi-
cientes enteros (Identidad de Bezout):
d = ax + by (1)
Exponemos a continuacin 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 := ai1 qiai (calculamos el cociente qi y el residuo ai+1
de la divisin entre ai1 y ai)
xi+1 := xi1 qixi (a partir de xi1,xi i qi, calculamos xi+1)
yi+1 := yi1 qiyi (a partir de yi1,yi i qi, calculamos yi+1)
hasta obtener un residuo ai = 0.
3. Si an es el primer residuo nulo, entonces d = an1 = axn1 + byn1.
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. Observacin
El Algoritmo 1.4 puedeaplicarse tambin a dospolinomios a(X),b(X) concoeficientes en un cuerpo K.Ver el ejemplo 1.3.
Ejemplo 1.2. Sea p = 7, y el cuerpo F7 = {0,1,2,3,4,5,6}. Para a = 3, b = 6 se tiene3 + 6 2 (mod 7), 3 6 4 (mod 7) y 31 5 (mod 7) (ntese que 1 = 1 7 2 3).
CC-BY-NC-ND PID_00200953 9 Cuerpos finitos
Ejemplo 1.3. Calcular el mximo comn divisor mcd(P(X),Q(X)) y expresar el resulta-do como combinacin de los polinomios iniciales P(X) y Q(X), donde P(X) y Q(X) sonpolinomios a coeficientes en F3: P(X) = X
7 + 2X2 + X + 1; Q(X) = X3 + 2X2.
La aplicacin del algoritmo de Euclides extendido nos da:
a0 = X7 + 2X2 + X + 1; a1 = X
3 + 2X2; a2 = X + 1; a3 = 1; a4 = 0
q1 = X4 + X3 + X2 + X + 1; q2 = X
2 + X + 2
x0 = 1; x1 = 0; x2 = 1; x3 = 2X2 + 2X + 1
y0 = 0; y1 = 1; y2 = 2X4 + 2X3 + 2X2 + 2X + 2; y3 = X
6 + 2X5 + X4 + X3 + X2
O sea que, 1 = mcd(P(X),Q(X)) y, adems:
(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, exis-
te un cuerpo finito con q elementos.
.
Proposicin 1.5. Sea K = Fq un cuerpo finito con q elementos, con
elemento neutro para la adicin 0K y elemento unidad para la multi-
plicacin 1K. Existe un primo p tal que K contiene al cuerpo Fp de los
enteros mdulo p.
Demostracin: El cuerpo K no puede tener caracterstica 0 (caso contrario
contendra al conjunto infinito {1K,2 1K, ,n 1K, }). K es pues de carac-
terstica prima p y contiene al subcuerpo {0K,1K,2 1K, (p 1) 1K} isomorfo
al cuerpo Fp de los enteros mdulo p.
.
Corolario 1.6. Sea Fq un cuerpo de caracterstica p. Existe un entero
positivo m tal que q = pm.
Demostracin: Fq admite una estructura de espacio vectorial sobre su sub-
cuerpo Fp, seam su dimensin (obviamente finita). Fijada una base cualquiera
de este espacio vectorial, Fq se identifica con el conjunto de vectores Fmp , con-
junto con cardinal pm.
Observacin
El cuerpo C de los nmeroscomplejos contiene las racesde todo polinomio concoeficientes en el cuerpo Qde los nmeros racionales.Sin embargo C no es unaclausura algebraica de Q yaque no se cumple lacondicin de minimalidad. Laclausura es un subcuerpo deC denominado cuerpo de losnmeros algebraicos.
El resultado anterior muestra que el cardinal de un cuerpo finito es siempre
potencia de un nmero primo. El siguiente teorema muestra que para cual-
quier potencia de un primo existe un cuerpo finito con ese cardinal y que tal
cuerpo es esencialmente nico.
.
Definicin 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 races en l y que es minimal con
esta propiedad. Tal clausura existe y es nica salvo isomorfismo.
CC-BY-NC-ND PID_00200953 10 Cuerpos finitos
.
Teorema 1.8. Para todo primo p y todo nmero natural m existe un
cuerpo finito con q = pm elementos. Tal cuerpo es nico salvo isomor-
fismo.
Demostracin: 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 races de F(X) en
una cierta clausura algebraica de Fp (no confundir con las races complejas de
tal polinomio, ntese que Fp no est contenido en los complejos). Tales races
son distintas (el polinomio F(X) no tiene races mltiples, ya que su derivada
no es nula: F(X) = qXq1 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, tambin ()q = (pues todos los dems miem-
bros del desarrollo de (a + b)q son mltiplos de p), luego la suma, diferencia,
producto y cociente de elementos de R estn en R.
Sea K otro cuerpo con q elementos. El grupo multiplicativo K = K {0} tiene
cardinal q1 y por tanto, todo elemento a K verifica aq1 = 1K, luego aq = a,
ecuacin que obviamente tambin verifica OK. Es decir, los q elementos de K
son races de Xq X y por tanto K puede identificarse con R.
Habitualmente, en criptografa 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 elemen-
tos, pero no una construccin explcita. El mtodo siguiente proporciona tal
construccin, que es formalmente anloga a la del cuerpo Fp como clases de
equivalencia de los enteros mdulo p.
Sea f (X) = Xm+fm1Xm1+ +f1X+f0 Fp[X] un polinomio mnico (coeficiente
del trmino 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 mdulo f (X). Un conjunto de representantes de estas clases viene
dado por el conjunto K de los q = pm polinomios a0+a1X+ +am1Xm1 Fp[X]
de grado menor que m (pues todo g(X) Fp[X] es equivalente al polinomio
resto de su divisin por f (X)).
Si denotamos K a la clase de equivalencia de X, es decir X (mod f (X)),
podemos identificar el elemento a0 + a1X + + am1Xm1 con a0 + a1 + +
am1m1 y K con el conjunto de estas expresiones.
Ntese que m + fm1m1 + + f1 + f0 0K y por tanto puede considerarse
como una raz del polinomio f (X) en K. Se tiene,
CC-BY-NC-ND PID_00200953 11 Cuerpos finitos
.
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.
Demostracin: El razonamiento es totalmente anlogo al de la proposicin
1.3 y los detalles se dejan como ejercicio. En particular el inverso de un ele-
mento no nulo se obtiene utilizando el algoritmo de Euclides extendido para
polinomios.
Nota
Se ha sealado que puede considerarse como raz de f (X). Dado que este polinomiode grado m tiene m races puede plantearse cul de ellas es . Sin embargo, a diferenciade lo que sucede con las races 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 smbolo, que se toma comoraz de f (X); una vez fijada esta raz, las restantes pueden expresarse en funcin de (verel ejemplo siguiente).
Ejemplo 1.4. Consideremos el polinomio irreducible X3 + X + 1 F2[X], y sea unaraz. Las otras dos races son entonces 2 y 2 + . Un cuerpo con 8 elementos estara
formado por los elementos:
F8 = {0,1,,1 + ,2,1 + 2, + 2,1 + + 2} (2)
con las siguientes tablas de adicin y multiplicacin:
+ 0 1 1 + 2 1 + 2 + 2 1 + + 2
0 0 1 1 + 2 1 + 2 + 2 1 + + 2
1 1 0 1 + 1 + 2 2 1 + + 2 + 2
1 + 0 1 + 2 1 + + 2 2 1 + 2
1 + 1 + 1 0 1 + + 2 + 2 1 + 2 2
2 2 1 + 2 + 2 1 + + 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 + + 21 1 1 + 2 1 + 2 + 2 1 + + 2
2 + 2 1 + 1 1 + + 2 1 + 2
1 + 1 + + 2 1 + 2 1 + + 2 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
1 + + 2 1 + + 2 1 + 2 1 + 2 2 1 +
Nota
El ejemplo anterior construye un cuerpo con 8 elementos utilizando el polinomio irre-
ducible X3 + X + 1 F2[X]. Pero una construccin anloga podra obtenerse a partir deuna raz del polinomio X3 +X2 + 1 F2[X] el cual es tambin 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 12 Cuerpos finitos
ms de un polinomio irreducible de grado m). En esta otra construccin se obtendrantablas aditivas y multiplicativas aparentemente diferentes.
Sin embargo, el teorema 1.8 garantiza que solo existe un cuerpo con 8 elementos. Cul
es la explicacin de esta aparente contradiccin? En realidad es un simple problema de
etiquetado de los elementos: en concreto, puede comprobarse que la asignacin =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 (Fq ,). 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 cclicos de orden p:
(Fq,+) Z/pZ Z/pZ. (3)
Demostracin: Como se ha indicado (Fq,+) es un espacio vectorial sobre
su subcuerpo primo Fp. Cualquier base de este espacio (por ejemplo, una ba-
se del tipo {1, ,m1} utilizada en el teorema 1.9 induce el isomorfismo
indicado.
1.2.1. Representacin 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, . . . ,p1}. 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 travs de un canal binario.
En esta forma aditiva los elementos pueden sumarse (sumando coordenada a
coordenada mdulo p) o multiplicarse escalarmente por un elemento de Fp.
Para estudiar la estructura multiplicativa, recordemos que, dado un grupo abe-
liano finito (G,), llamamos orden de x G al orden del subgrupo engendra-
do 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, enton-
ces existe un elemento x G de orden n.
CC-BY-NC-ND PID_00200953 13 Cuerpos finitos
Demostracin: Sea n = pe11 pemm la descomposicin de n en factores primos.
Como peii aparece en la factorizacin, existe xi G de orden kipeii para un
cierto entero natural ki. Entonces el elemento xkii tendr orden p
eii y por tanto
x =Qm
i=1 xkii tendr orden exactamente n.
.
Teorema 1.12 (Estructura multiplicativa). El grupo multiplicati-
vo (Fq ,) es cclico de orden q 1.
Demostracin: Sea n el exponente de Fq . En virtud del lema anterior debe
existir un elemento de orden n. Por tanto n q 1 = #Fq . Por otra parte, por
ser nmltiplo del orden de todo elemento, los q1 elementos de Fq satisfacen
la ecuacin 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 cclico.
.
Definicin 1.13 (Elemento primitivo). Llamaremos elemento pri-
mitivo de Fq a un generador del grupo cclico (Fq ,).
Nota
La nocin de elemento primitivo en el contexto de un grupo cclico finito de orden n yla notacin (n) para el nmero de tales elementos primitivos puede encontrarse en elmdulo 5 del curso Criptografa de la UOC. Tal nmero es importante en matemticas yser utilizado en otras partes de este curso, por lo que damos a continuacin su definicin
y algunas de sus propiedades.
.
Definicin 1.14 (Funcin de Euler). Para todo nmero natural n se
denota (n) al nmero de elementos a; 0 < a < n tales que mcd(a,n) =
1. La funcin as obtenida se denomina funcin de Euler.
.
Proposicin 1.15. La funcin de Euler verifica las siguientes propie-
dades:
1) Si p es un nmero primo, (p) = p 1.
2) Si p es un nmero primo y r un nmero natural, (pr) = pr pr1 =
pr1(p 1).
3) Si m,n son nmeros naturales primos entre s (es decir, mcd(m,n) =
1), (mn) = (m)(n)
CC-BY-NC-ND PID_00200953 14 Cuerpos finitos
La demostracin es sencilla y se deja como un ejercicio.
.
Corolario 1.16. Sea n = pr11 . . . prss la factorizacin prima del nmero
natural n. Se tiene:
(n) = n Yi
(1 1/pi) (4)
El corolario 1.16 muestra que el clculo de (n) es fcil si se conoce la fac-
torizacin de n. Por contra, sin conocer tal factorizacin, este clculo es un
problema computacionalmente dificil.
1.2.2. Representacin multiplicativa
En virtud del teorema 1.12, si es un elemento primitivo de Fq, entonces
Fq = {
i | i = 1, . . . ,q 1}. Esta representacin ser fundamental en los sistemas
criptogrficos basados en el problema del logaritmo discreto.
Ejemplo 1.5 . Para q = 11, = 2 es un elemento primitivo de F11.
Observacin
No se conoce ningnalgoritmo eficiente para elclculo de un elementoprimitivo, ni siquiera en elcaso de los cuerpos Fp, pprimo.
Ejemplo 1.6 . Como en el ejemplo 1.4, consideremos el polinomio irreducible X3 + X +1 F2[X], y sea una raz.
Para saber si es un elemento primitivo, en F8 deberamos calcular su orden y ver si es
mximo. 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.
Luego es un elemento primitivo y la tabla de equivalencias entre la representacin
vectorial (o polinomial) y exponencial es:
Observacin
Observar que al escribir unpolinomio como vector,utilizando los coeficientes desu expresin aditiva, hemosempezado por el trmino degrado cero como primeracoordenada.
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
CC-BY-NC-ND PID_00200953 15 Cuerpos finitos
2. Bases de cuerpos finitos.
Como se ha indicado, los elementos de Fq, q = pm pueden expresarse como
combinacin lineal, con coeficientes en Fp, de los elementos de una base.
Desde un punto de vista computacional, dos tipos de bases son especialmente
importantes.
.
Definicin 2.1 (Base polinmica). Se denomina base polinmica
del cuerpo Fq a una base del tipo {1, ,m1}, con raz de un
polinomio mnico e irreducible con coeficientes en Fp.
El nmero de bases polinmicas de Fq ser pues igual al nmero de polino-
mios mnicos e irreducibles de grado m con coeficientes en Fp. Tal nmero
puede determinarse explcitamente.
.
Proposicin 2.2. Xq X es el producto de todos los polinomios irre-
ducibles sobre Fp cuyo grado divide a m.
Demostracin: Sea g(X) Fp[X] un polinomio mnico e irreducible de gra-
do d|m. Es decir m = dd. En virtud del teorema 1.9 las races de g(X) determi-
nan un cuerpo con Fpd elementos y por tanto, por el teorema 1.8, son races
de Xpd
X, luego g(X) divide a Xpd
X. Se tiene pm 1 = (pd 1)(pd(d1) +pd(d
2) +
pd + 1) es decir pd 1 divide a pm 1. Un razonamiento anlogo con X en
lugar de p, muestra que Xpd1 1 divide a Xp
m1 1 luego Xpd
X y por tanto
g(X) divide a Xq X.
Recprocamente, un razonamiento similar prueba que si g(X) es un polinomio
mnico e irreducible que divide a Xq X, su grado es un divisor de m.
.
Corolario 2.3. Si denotamos por Np(d) el nmero de polinomios irre-
ducibles de grado d sobre Fp, se tiene,
q =Xd|m
dNp(d). (5)
CC-BY-NC-ND PID_00200953 16 Cuerpos finitos
El nmero buscado Np(m) figura como sumando en la expresin anterior. Vea-
mos cmo despejarlo.
.
Definicin 2.4 (Funcin de Moebius). Llamaremos funcin de Moe-
bius a la funcin de variable natural, : N {1,0,1} definida del
modo siguiente: si n N y n =Qs
i=1 peii es su descomposicin en factores
primos, entonces
(n) =
8>>>>>>>>>>>:
1 si n = 1;
0 si ei 2 para algn valor de i;
(1)s si ei = 1 para todo valor de i.
(6)
.
Lema 2.5. Si n N, se verifica que
Xd|n
(d) =
8>>>:
1 si n = 1;
0 si n > 1.
(7)
Demostracin: 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 defini-
cin de la funcin de Moebius,
Xd|n
(d) = (1) +sXi=1
(pi) +X
1i
CC-BY-NC-ND PID_00200953 17 Cuerpos finitos
.
Lema 2.6 (Frmula de inversin de Moebius). Sea f una funcin
de variable natural con valores en un grupo abeliano. Para n N defi-
namos g(n) mediante
g(n) =Xd|n
f (d). (8)
Se verifica que
f (n) =Xd|n
(d)g(n
d) =
Xd|n
(n
d)g(d). (9)
Demostracin:
Xd|n
(d)g(n
d) =
Xd|n
(d)Xe|(n/d)
f (e)
=Xe|n
Xd|(n/e)
(d)f (e)
=Xe|n
f (e)Xd|(n/e)
(d)
= f (n).
donde para la ltima igualdad hemos tenido en cuenta el lema 2.5.
.
Teorema 2.7. El nmero de polinomios irreducibles de grado m sobre
Fp es
Np(m) =1
m
Xd|m
(d)pm/d =1
m
Xd|m
(m
d)pd. (10)
Demostracin: Basta aplicar la frmula de inversin de Moebius a la funcin
f (m) = mNp(m).Observacin
Un polinomio irreducible degrado m puede obtenersetomando polinomiosarbitrarios y aplicndoles untest de irreducibilidad (Lidl yNiederreiter, 1997). El valorNp(m) dado por el teorema2.7 proporciona unaestimacin de la probabilidadde xito de tal bsquedaaleatoria.
Ejemplo 2.1. Para p = 2 el nmero de polinomios de grado m es:
1) 1 si m = 2. El polinomio: X2 + X + 1.
2) 2 si m = 3. Los polinomios: X3 + X + 1 y X3 + X2 + 1.
3) 3 si m = 4. Los polinomios: X4 + X + 1, X4 + X3 + 1 y X4 + X3 + X2 + X + 1.
4) etc.
CC-BY-NC-ND PID_00200953 18 Cuerpos finitos
.
Definicin 2.8 (Base Normal). Se denomina base normal de Fq a
una base del tipo {,p, ,pm1
} con Fq.
Como se ver en el apartado siguiente, las bases normales son muy eficientes
para el cmputo de la exponenciacin en Fq, operacin bsica en los algorit-
mos criptogrficos basados en el problema del logaritmo discreto. Para tener
una base normal es necesario un elemento cuyas potencias p-simas sucesi-
vas sean linealmente independientes.
Ejemplo 2.2. Sea q = 8 = 23, raz del polinomio irreducible,
X3 +X+1. En este caso {,2,4} no es base normal (pues ni siquiera es base, ya quelos tres elementos son linealmente dependientes).
X3 + X2 + 1. En este caso {,2,4} es base normal.
Lectura recomendada
Sobre el teorema de la base
normal podis ver la obra
de Lidl y Niederreiter (1997)
o la de Menezes (1993).
En general, no es obvia la existencia de un elemento generando una base
normal. Se tiene, sin embargo, el teorema 2.9.
.
Teorema 2.9 (Teorema de la base normal). Existe una base nor-
mal para todo cuerpo finito.
Evaluemos el nmero de bases normales. Supongamos fijada una tal base nor-
mal B = {,p, . . . ,pm1
} (cuya existencia garantiza el teorema 2.9). Un cambio
de base de B a una nueva base B = {0,1, . . . ,m1} viene determinado por
una matriz mm inversible C = (cij), cij Fp.
Observacin
Comenzar con 0 lossubndices de los elementosde la base B y de loscomponentes de la matrizcirculante es por coherenciacon los exponentes de la basenormal B: p0,p1, . . . ,pm1
Veamos qu condicin debe cumplir C para que la nueva base B sea tambin
normal.
.
Definicin 2.10 (Matriz circulante). Se denomina matriz circulan-
te (con coeficientes en un cuerpo o anillo) a una matriz del tipo:
[a0,a1, . . . ,am1] =
0BBBBBBBBBBBBBB@
a0 a1 . . . am1
am1 a0 . . . am2
. . . .
. . . .
a1 a2 . . . a0
1CCCCCCCCCCCCCCA
. (11)
CC-BY-NC-ND PID_00200953 19 Cuerpos finitos
Es decir, la matriz queda determinada por su primera fila, ya que las siguientes
se deducen cada una de la anterior mediante una permutacin cclica de sus
elementos, que desplaza cada coordenada una posicin a la derecha.
.
Teorema 2.11. La base B es normal si, y solo si, la matriz C de cambio
de base es circulante
Demostracin: Supongamos que la matriz es circulante, es decir C = [a0,a1,
. . . ,am1] lo que implica que cij = aji luego,
i =Xj
ajipj =
0@X
j
ajipji
1A
pi
=
0@X
j
ajpj
1A
pi
= pi
0
lo que muestra que la base B es normal.
Si recprocamente suponemos B normal, sea 0 =P
j c0jpj . Se tendr:
i = pi
0 =Xj
c0jpi+j =
Xj
c0,jipj (12)
pero tambin (por definicin) i =P
j cijpj , lo que muestra que la matriz C es
circulante.
Lectura recomendada
Para la determinacin del
nmero de bases normales
del cuerpo Fq podis ver la
obra de Lidl y Niederreiter.
El nmero de bases normales del cuerpo Fq ser pues igual al nmero de ma-
trices mm circulantes e invertibles con coeficientes en Fp.
CC-BY-NC-ND PID_00200953 20 Cuerpos finitos
3. Computacin en cuerpos finitos.
El propsito de este apartado es mostrar cmo pueden realizarse, con los ele-
mentos de un cuerpo finito Fq, las operaciones aritmticas habituales y cul
es el coste computacional de las mismas.
3.1. Aritmtica en cuerpos finitos
Como se ha indicado en el teorema 1.10, fijada una base de Fq sobre Fp,
todo elemento a Fq puede ser representado como un vector de la forma
a = (a1,a2, . . . ,am), con ai {0,1, . . . ,p 1}. La adicin o substraccin de dos
elementos a, b se realiza sumando o restando coordenada a coordenada y re-
duciendo el resultado mdulo p.
3.1.1. Multiplicacin
Fijada una base cualquiera B = {v1,v2, . . . ,vm} y dos elementos de Fq: a = a1v1 +
a2v2 + + amvm, b = b1v1 + b2v2 + + bmvm, (que podemos identificar con los
vectores a = (a1,a2, ,am), b = (b1,b2, ,bm)), se tiene:
c = a b = (Xi
aivi)(Xj
bjvj) =Xij
aibj(vivj) =Xij
aibj(Xk
tkijvk) (13)
Luego, denotando Tk = (tkij), k = 1,2, . . . ,m, se tienen m matrices mm deno-
minadas tablas de multiplicacin. Si c = c1v1 + c2v2 + + cmvm, las coordenadas
ci vienen dadas por la ecuacin matricial:
Observacin
En la ecuacin 14 la bt
denota el vector traspuestodel b (en este caso un vectorescrito verticalmente).
ck = aTkbt . (14)
Las tablas de multiplicacin determinan pues el producto. Este puede imple-
mentarse bien en software, almacenando las m tablas, bien en dispositivos
hardware especficos, que constan de m circuitos cada uno de los cuales da,
como salida a los inputs a,b Fq, una componente ck del producto.
Usualmente se emplean bases particulares, como las polinmicas o las norma-
les, ya descritas. Veamos las caractersticas especficas de estos dos casos:
CC-BY-NC-ND PID_00200953 21 Cuerpos finitos
Base polinmica: Sea {1,, ,m1}, con raz del polinomio (mnico
e irreducible) f (X). En este caso, dados a = a0 + a1 + + am1m1 y b =
b0 + b1 + + bm1m1, el clculo de a b implica dos operaciones:
1) Multiplicacin de a y b como si fuesen polinomios en X.
2) Reduccin del polinomio obtenido, de grado a lo sumo 2m 2, mdulo
f (X) (es decir, realizar la divisin eucldea por f (X) y tomar el resto).
Ejemplo 3.1. Sea el cuerpo F8 y raz de f (X) = X3+X+1 y los elementos a = 1+2, b =1 + .
1) El producto de los polinomios a(X) = X2 + 1 y b(X) = X + 1 da como resultado elpolinomio c(X) = X3 + X2 + X + 1.
2) La division de c(X) por f (X) da como resto X2.
Luego a b = 2.
Base Normal: Si se utiliza una base normal B = {0 = ,1 = p, . . . ,m1 =
pm1
}, las m tablas de multiplicacin Tk = (tkij) verifican la siguiente rela-
cin:
.
Lema 3.1. Para 0 < l m 1 se tiene tlij = t0il,jl. Es decir, la tabla Tl se
deduce de la T0 por desplazamiento de l posiciones en filas y columnas.
Demostracin: Por definicin de las tablas ij =P
k tkijk. Elevando ambos
miembros a pl se tiene que pl
i pl
j = iljl =P
k tkijkl. Pero, por definicin,
iljl =P
k tkil,jlk. Igualando los coeficientes de 0 en ambas expresiones se
tiene el resultado.
En consecuencia, si se tiene un algoritmo (o en hardware un circuito electr-
nico) para calcular la primera coordenada c0 del producto de los elementos
a,b Fq el mismo algoritmo o circuito calcula la coordenada cl con las coor-
denadas de a y b desplazadas l posiciones.
3.1.2. Divisin
La divisin de dos elementos a,b Fq, b 6= 0, implica la multiplicacin de a
por el inverso del elemento b. Si se emplea una base polinmica, dicho inverso
puede computarse utilizando el algoritmo de Euclides 1.4 para polinomios.
Ejemplo 3.2. Sea f (X) = X3 + X + 1, b = 1 + 2. El algoritmo de Euclides proporciona:a2 = 1,a3 = 0, x2 = 1, y2 = X y por tanto 1 = f (X) 1 + (X2 + 1)X, luego b1 = .
CC-BY-NC-ND PID_00200953 22 Cuerpos finitos
3.1.3. Exponenciacin
* A su vez necesarios en el
sistema criptogrfico RSA;
consultar la obra de Koblitz
(1994).
Clculos del tipo an (mod m), con a,n,m Z (o bien del tipo an, a Fq, n
N) son una herramienta fundamental en los sistemas criptogrficos basados
en el problema del logaritmo discreto y en otros campos como los tests de
primalidad*. En principio podra realizarse este clculo multiplicando a por s
mismo n veces y posteriormente reduciendo mdulom el resultado obtenido.
Ahora bien, para n grande, un clculo del tipo anterior sera impracticable por
dos razones:
1) El nmero excesivo de multiplicaciones.
2) Los clculos intermedios de estas multiplicaciones proporcionan nmeros
de tamao creciente, que pronto superarn la capacidad de almacenamiento
del computador.
Existe sin embargo un algoritmo (multiplicacin y elevacin al cuadrado) que
permite evitar estos dos inconvenientes:
Sea n = s0 + s12 + sk12k1 la expresin binaria de n y sea b := 1,
.
Algoritmo 3.2 (Multiplicar y elevar al cuadrado).
Desde j = k 1 hasta 0
Si sj = 1 entonces b := ba (mod m).
Si j > 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 expresin del exponente n en otra base diferentede 2 (por ejemplo, para base 3 se tendra un algoritmo donde en lugar de elevar al
cuadrado se elevara al cubo).
2) La reduccin mdulo m puede sustituirse por operacin en un cuerpo finito Fq. Enparticular para m = p primo la reduccin mdulo p es la operacin en el cuerpoprimo Fp.
CC-BY-NC-ND PID_00200953 23 Cuerpos finitos
La exponenciacin puede simplificarse, especialmente en el caso de cuerpos
binarios, utilizando bases normales. En efecto se tiene:
.
Lema 3.3. Sean {a0,a1, . . . ,am1} las coordenadas de un elemento a Fqen la base normal {,p, . . . ,p
m1
}. El elemento ap tiene por coordena-
das (am1,a0,a1, . . . ,am2).
Demostracin: Se tiene (teniendo en cuenta que todos los dems miembros
del desarrollo de (a + b)q son potencia de p y por tanto nulos en caracterstica
p, que api = ai y que
pn = q = ) que:
(a0+a1p+ +am1
pm1 )p = a0p+a1
p2+ +am1pm = am1+a0
p+ +am2pm1
El lema anterior muestra que la elevacin a la potencia p implica simplemente
una permutacin circular de los coeficientes y por tanto, su coste computacio-
nal es despreciable. Si p = 2 es la elevacin al cuadrado, pieza fundamental en
el algoritmo 3.2, la que tiene coste cero.
3.2. Complejidad de la aritmtica en cuerpos finitos
Veamos cmo obtener una estimacin del coste de los algoritmos aritmti-
cos descritos en un cuerpo finito Fq. La disciplina que estudia el coste de los
algoritmos y problemas matemticos se denomina teora de la complejidad
computacional. Si se desea medir la cantidad de computacin necesaria pa-
ra ejecutar un algoritmo, habr que tener una unidad de medida. Dado que
un computador reduce cualquier clculo a sumas binarias elementales, puede
tomarse tal suma como unidad.
.
Definicin 3.4 (Operacin bit). Se denomina operacin bit a la adi-
cin de dos elementos en el cuerpo F2, es decir, a la suma binaria (m-
dulo 2) de dos nmeros iguales a 0 1 (bits).
Para medir en operaciones bit el tiempo o cantidad de computacin de un algo-
ritmo, la teora de la complejidad computacional introduce dos precisiones:
1) El tiempo debe ser funcin de la longitud de los datos (inputs). Tales datos
son siempre nmeros naturales (o reducibles a ellos: por ejemplo, un elemento
de un cuerpo finito con cardinal q = pm queda determinado por m nmeros
naturales menores que p).
CC-BY-NC-ND PID_00200953 24 Cuerpos finitos
2) El tiempo de ejecucin de un algoritmo, para una longitud dada de los da-
tos, variar en cada caso concreto. Se adopta el criterio del caso peor tomando
una cota vlida para toda instancia particular de dicha longitud.
.
Definicin 3.5 (Longitud binaria de un nmero). Se denomina
longitud (binaria) k de un nmero natural n , al nmero de dgitos de
su expresin en base 2. Dicha longitud es el nmero natural k tal que
2k1 n < 2k y por tanto k = log2 n + 1. Ntese que la longitud de
un nmero es tambin el nmero de bits de memoria necesarios para
almacenarlo en un computador.
.
Definicin 3.6 (Notacin 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).
.
Definicin 3.7 (Complejidad Polinmica). Un algoritmo con da-
tos iniciales: los enteros n1,n2, . . . ,ns , de longitudes k1,k2, . . . ,ks , se llama
de complejidad polinmica si existe un polinomio P en s variables tal que
el tiempo de ejecucin de dicho algoritmo, medido en operaciones bit,
es O(P(k1,k2, . . . ,ks)).
Algoritmos eficientes
Los algoritmos decomplejidad polinmica sedenominancomputacionalmenteeficientes o buenos, ya que elcomputador puedeejecutarlos en un tiemporazonable, por oposicin a losalgoritmos cuya complejidades exponencial en la longitudde los datos.
Como veremos, las operaciones aritmticas usuales en cuerpos finitos, en par-
ticular las implicadas en los algoritmos criptogrficos, tienen una complejidad
polinmica. Dado que las operaciones en cuerpos finitos se remiten a opera-
ciones con nmeros enteros, veamos previamente la complejidad de algunos
algoritmos bsicos con enteros.
.
Proposicin 3.8.
El tiempo necesario para sumar dos nmeros naturales de longitud
binaria k es O(k). La adicin de nmeros naturales tiene pues com-
plejidad lineal en la longitud de los datos.
El tiempo necesario para multiplicar dos enteros naturales de longi-
tudes k, l , l k es O(k2). La multiplicacin tiene pues una compleji-
dad cuadrtica en la longitud de los datos.
CC-BY-NC-ND PID_00200953 25 Cuerpos finitos
Observacin
Debe sealarse que elalgoritmo habitual demultiplicacin no es el mejoralgoritmo conocido pararealizar esta operacin. Existeotro, debido a Schnhage yStrassen, con complejidadO(k log(k) log log(k))
Demostracin:
1) Puede siempre suponerse la misma longitud para ambos sumandos, aa-
diendo eventualmente ceros a la izquierda de la representacin binaria del de
menor longitud. La suma se obtiene entonces realizando k sumas binarias, es
decir, por definicin, k operaciones bit.
2) Sea l k. Con la regla habitual de multiplicacin: colocar el nmero me-
nor debajo del mayor y multiplicar cada dgito de aquel por este, colocar los
resultados en filas desplazadas cada una de ellas una posicin a la izquierda
respecto de la anterior y sumando, a lo sumo, las l filas, de longitud k + l, (te-
niendo en cuenta los kl desplazamientos), se tiene un nmero de operaciones
bit,
O(l(k + l)) = O(2kl) = O(2k2) = O(k2)
Nota
La operacin de substraccin o resta tiene obviamente el mismo tiempo de ejecucin
que la suma. La divisin, con la regla habitual, se reduce a multiplicaciones y diferencias
y tiene pues igual tipo de complejidad que la multiplicacin, es decir, cuadrtica. Sin
embargo, debe recordarse que la estimacin de la complejidad, dada por la notacin O,implica una constante, por lo que dos algoritmos con igual complejidad pueden tener de
hecho costes muy diferentes. Es el caso de la divisin, bastante ms costosa que la mul-
tiplicacin. Ello justifica el tratar de evitar o limitar al mximo el nmero de divisiones;
en el caso de la criptografa con curvas elpticas, 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 clculo de inversos en Fp.
Obsrvese que en el algoritmo 1.4 los restos ai, obtenidos al iterar el paso 2,
forman una sucesin decreciente. Por tanto, el algoritmo finaliza necesaria-
mente en un nmero finito de etapas. Ms concretamente se tiene,
.
Lema 3.9. Si a b, el nmero de etapas necesarias en la ejecucin del
algoritmo de Euclides extendido es O(log(a)).
Demostracin: Basta probar que los restos ai verifican la relacin ai+2 < 12ai,
lo que implica que el nmero de etapas es, a lo sumo, 2log(a). Ahora bien,
si ai+1 12ai, entonces ai+2 < ai+1
12ai. Si ai+1 >
12ai, la divisin eucldea
proporciona ai = 1ai+1 + ai+2, con lo que tambin en este caso, ai+2 = ai ai+1
Recommended