02 criptografia avanzada (modulo 1)

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.


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.


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}.


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).


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.


.

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,


.

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


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.


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)


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


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)


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


.

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.


.

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)


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.


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:


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 = .


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.


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).


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.


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

02 criptografia avanzada (modulo 1)

Documents