Trabajo Dirigido en Estadística y Computación

Licenciatura en Matemáticas

Curso 2012-2013

El logaritmo discreto y sus

aplicaciones en Criptografía

Alumna: Jennifer Santamaría Fernández

Director: Daniel Sadornil Renedo

Facultad de Ciencias

Universidad de Cantabria
Índice general

1. Introducción 3
2. Criptografía. Denición y desarrollo. 5
3. Preliminares algebraicos 10
4. Criptografía basada en PLD 13
4.1. El problema del logaritmo discreto . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2. Criptosistemas basados en el logaritmo discreto . . . . . . . . . . . . . . . . . . 14
4.2.1. Intercambio de claves de Die-Hellman (DH) . . . . . . . . . . . . . . . 14
4.2.2. Criptosistema de Massey-Omura . . . . . . . . . . . . . . . . . . . . . . 15
4.2.3. Criptosistema de ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2.4. Algoritmo de rma de ElGamal . . . . . . . . . . . . . . . . . . . . . . . 18
4.2.5. Algoritmo de rma digital (DSA) . . . . . . . . . . . . . . . . . . . . . . 19
4.2.6. Algoritmo de Blum-Micali . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.7. Criptosistema de Ciss-Cheikh-Sow . . . . . . . . . . . . . . . . . . . . . 21

5. Métodos de cálculo del logaritmo discreto 23

5.1. Algoritmos Genéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.1. Fuerza Bruta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.2. Algoritmo de Shanks: Baby step-Giant step . . . . . . . . . . . . . . . 24
5.1.3. Algoritmo ρ de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.1.4. Algoritmo del canguro de Pollard . . . . . . . . . . . . . . . . . . . . . . 33
5.2. Algoritmo de Silver-Pohlig-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3. Index-Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3.1. Factorización de polinomios en cuerpos nitos . . . . . . . . . . . . . . . 41

Bibliografía 52

2
Capítulo 1

Introducción
En la actualidad, mantener en secreto ciertas informaciones es una parte fundamental e
imprescindible de prácticamente cualquier acción cotidiana, ya sea pagar una compra con tar-
jeta de crédito, consultar el correo electrónico o enviar un mensaje de texto. Precisamente
ese es uno de los objetivos de la Criptografía y, para ello, se necesitan herramientas que per-
mitan llevar a cabo dicha tarea. Dichas herramientas son aportadas, principalmente, por las
Matemáticas. El uso de problemas matemáticos difíciles o imposibles de resolver bajo ciertas
condiciones, con las herramientas de cálculo disponibles hoy en día, es algo habitual en Cripto-
grafía. Uno de los problemas matemáticos en los que se basan algunos sistemas criptográcos
es el tópico de este trabajo: el logaritmo discreto.

Sea G un grupo abeliano nito (multiplicativo) y sea g un elemento de orden n de G. Dado

un elemento a perteneciente al subgrupo generado por g , se dene el logaritmo discreto de a
en base g como el entero k , 0 ≤ k ≤ n − 1, tal que:

gk = a
Aunque el logaritmo discreto se ha denido en un grupo multiplicativo y en este trabajo
sólo se consideran grupos de este tipo, se puede denir de forma general en un grupo. Es
posible denir el logaritmo discreto en grupos aditivos como el conjunto de puntos de una
curva elíptica. En tal caso, se habla de logaritmo discreto elíptico. Los algoritmos de cálculo
explicados a lo largo de este trabajo son todos adaptables a este caso salvo el Index-Calculus.
Además, existen otros algoritmos especícos.

Para abordar no sólo la resolución, sino también la utilidad del logaritmo discreto, el traba-
jo se estructura como sigue. En el capítulo 2, se exponen los pilares básicos de la Criptografía
con el objetivo de situar el área de aplicación del tema del trabajo. Se presenta en dicho capí-
tulo una visión general de la Criptografía: objetivos, aplicaciones, tipos de ataques, tipos de
seguridad, etc. Además, se expone la diferencia entre la Criptografía de clave privada y de clave
pública, siendo esta última donde el logaritmo discreto juega un papel fundamental. Se cie-
rra el capítulo con un pequeño resumen del desarrollo de la Criptografía a lo largo de la historia.

En el capítulo 3, se hace un breve repaso de aquellos resultados fundamentales del Álgebra

y de la Teoría de Números que estarán presentes a lo largo de todo el trabajo y que serán
necesarios para comprender algunas aplicaciones del logaritmo discreto en Criptografía y di-
versos métodos de resolución del problema.

3
CAPÍTULO 1. INTRODUCCIÓN 4

Una vez tratadas las cuestiones preliminares, se introduce el problema del logaritmo discre-
to en el capítulo 4. Se pone de maniesto la dicultad que entraña su resolución y se presentan
algunos sistemas criptográcos basados en el mismo como, por ejemplo, el criptosistema de
Massey-Omura o el de ElGamal. Asimismo se estudian el algoritmo de intercambio de claves
de Die-Hellman y dos algoritmos de rma digital (DSA y de ElGamal) que también basan
su seguridad en el problema del logaritmo discreto.

En el capítulo 5, se estudian algunos de los métodos más importantes y conocidos pa-

ra resolver el problema del logaritmo discreto. Se comienza por los métodos genéricos: la
fuerza bruta, el algoritmo de Shanks y los algoritmos ρ y λ de Pollard. Estos algoritmos no
aprovechan ninguna característica del grupo. A continuación se presenta el algoritmo de Silver-
Pohlig-Hellman que resuelve el problema del logaritmo discreto de forma eciente si el cardinal
del grupo tiene todos sus factores primos pequeños (menores que una cuota adecuada). Se con-
cluye el capítulo con la exposición del Index-Calculus.

El Index-Calculus es el más potente de los métodos presentados y, a diferencia del al-

goritmo de Silver-Pohlig-Hellman, no necesita que el grupo donde se trabaja cumpla ninguna
propiedad para ser ecaz. Sin embargo, para poder utilizar el Index-Calculus, es imprescindi-
ble disponer de algoritmos de factorización en el grupo. De hecho, en el capítulo 5 se incluyen
algunos métodos ecaces para factorizar polinomios necesarios para aplicar el Index-Calculus
en ciertos grupos.
Capítulo 2

Criptografía. Denición y desarrollo.

La palabra Criptografía tiene su origen etimológico en las palabras griegas krypto (ocul-
to") y graphos (escribir"), lo que da una idea clara de su denición clásica. La Criptografía
se denía como el arte de escribir mensajes en clave secreta o de modo enigmático para evitar
que su contenido fuese inteligible por un posible intruso en la comunicación. Es decir, el único
objetivo de la Criptografía era conseguir la condencialidad de los mensajes. En 1949, Shan-
non publicó el artículo Una teoría matemática de las comunicaciones [26] y la Criptografía
comenzó a ser considerada una ciencia aplicada que requiere conocimientos de otras ciencias
como las Matemáticas o la Teoría de la Información.

A nales del siglo XX, el desarrollo de la informática e Internet dieron lugar a grandes
cambios en en Criptografía. Por ejemplo, la gran cantidad de información a disposición de
muchos usuarios hace necesario que los datos estén protegidos durante su almacenamiento, no
sólo durante la transmisión. Es por eso que, actualmente, la Criptograa tiene otros objetivos
aparte de la transmisión secreta de la información. Este tipo de aplicaciones se engloba dentro
de lo que se denominan protocolos criptográcos. Un protocolo criptográco es un conjunto
bien denido de etapas, implicando a dos o más partes y acordado por ellas, designado para
realizar una tarea especíca que utiliza como herramienta algún algoritmo criptográco. He
aquí algunos ejemplos:

Protocolos de autenticación. Hay dos tipos de autenticación: autenticación de men-

saje y autenticación de usuario. La primera asegura que el contenido del mensaje no
ha sido alterado. La segunda, certica la identidad del remitente.

Protocolos para compartir secretos. La nalidad de este tipo de protocolos es distribuir un

cierto secreto entre un conjunto P de participantes de manera que ciertos subconjuntos
prejados de P puedan, uniendo sus participaciones, recuperar dicho secreto.

Pruebas de conocimiento cero: hacen posible que un individuo pueda convencer a otro
de que posee cierta información sin revelarle nada sobre el contenido de la misma.

Transacciones electrónicas seguras: permiten realizar de manera electrónica segura las

operaciones bancarias habituales, rma electrónica de contratos...

Votaciones electrónicas: permiten realizar un proceso electoral electrónicamente, garan-

tizando la privacidad de cada votante y la imposibilidad de fraude.

Así pues, la Critografía ya no sólo se utiliza para preservar la condencialidad, sino que
con ella se buscan también otros objetivos:

5
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 6

Autenticación. Es la propiedad que me permite identicar el generador de la información

(y de esta manera evitar posibles suplantaciones de identidad).

Integridad. Es la propiedad que busca mantener los datos libres de modicaciones no

autorizadas.

No repudio. Proporciona protección contra la interrupción, por parte de alguna de las

entidades implicadas en la comunicación, de haber participado en toda o parte de la
comunicación. Esto evita que el emisor niegue el envío de cierta información o que el
receptor niegue que la recibió.

Sin embargo, la Criptografía corresponde sólo a una parte de la comunicación secreta.

Si se quiere mantener en secreto la comunicación es porque existe la posibilidad de que un
enemigo intercepte el mensaje y este sea revelado. El conjunto de técnicas utilizadas por el
enemigo para descifrar los mensajes secretos es una ciencia conocida como Criptoanálisis. La
Criptología es el conjunto la Criptografía y el Criptoanálisis.

Contra un mensaje secreto es posible encontrar dos tipos básicos de amenazas: la pasiva
y la activa. En la primera de ellas, el enemigo simplemente quiere acceder a la información,
mientras que en la segunda pretende llevar a cabo una modicación o falsicación de la misma
o incluso una interrupción de la comunicación. Es decir, el primer tipo de amenaza compromete
la condencialidad y el segundo, la integridad y autenticidad de los mensajes. En cuanto a
la seguridad de la comunicación, es conveniente conocer la situación del enemigo y de qué
herramientas dispone. En este contexto podrían distinguirse cuatro tipos de ataque:

Ataque sólo con texto cifrado. Se trata de la peor situación posible para el criptoanalista
pues, a partir del mensaje cifrado, éste desea conocer el mensaje original.

Ataque con texto original conocido. El criptoanalista tiene acceso a una correspondencia
entre un texto original y su cifrado.

Ataque con texto original escogido. El enemigo puede obtener el cifrado de cualquier
texto original que cumpla ciertas condiciones prejadas por él.

Ataque con texto cifrado escogido. El criptoanalista puede obtener los mensajes originales
correspondientes a determinados mensajes cifrados que elija (pero no el mensaje que
desea descifrar).

Ante el ataque de un criptoanalista, un criptosistema puede presentar uno de los siguientes

tipos de seguridad:

Seguridad teórica o perfecta. El criptosistema es seguro contra cualquier enemigo que

tenga recursos y tiempo ilimitados.

Seguridad práctica o computacional. El criptosistema es seguro contra aquellos enemigos

que tengan insuciente tiempo y/o recursos.
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 7

Seguridad probable. La seguridad del criptosistema aún no ha sido demostrada, pero por
el momento no ha sido roto.

Seguridad condicional. El criptosistema es seguro hasta que se desarrollen nuevos o

mejores métodos de criptoanálisis.

La forma en que la Criptografía protege la información es variando su forma. Dado un

texto original se llama cifrado a una transformación del mismo en el llamado texto cifrado.
La transformación que permite recuperar el texto original a partir del texto cifrado se llama
descifrado. La familia de transformaciones posibles se denomina sistema criptográco o crip-
tosistema y cada una de ellas está determinada por un parámetro llamado clave. De manera
más formal:

Denición 2.1. Un sistema criptográco o criptosistema es una terna (M, C, K), donde M es
el conjunto de mensajes originales, C es un conjunto de mensajes cifrados y K es un conjunto
nito de claves, junto con dos funciones:
c : M × K −→ C y d : C × K −→ M
tales que d(c(M, k), k) = M para todo (M, k) ∈ M × K.
Las funciones c y d reciben el nombre de funciones de cifrado y descifrado respectivamente.
Los criptosistemas pueden dividirse en sistemas de clave privada y sistemas de clave públi-
ca. En los sistemas de clave privada las personas que comparten el criptosistema comparten o
guardan en secreto las funciones c y d (o, al menos, la clave de que dependen). Por el contrario,
en los sistemas de clave pública cada usuario i del criptosistema tiene un par de claves (ci ,di ).
La primera de ellas, ci , es la clave pública y es la que utiliza cualquier otro usuario j que quiera
transmitir un mensaje M a i. Esto quiere decir que j cifra el mensaje en la forma C = ci (M ).
La segunda clave, di , es privada y empleada por i para recuperar los mensajes cifrados que
recibe. Esto es, M = di (C) = di (ci (M )).

En criptografía de clave pública es importante notar que la clave pública se obtiene a partir
de la privada (o viceversa). Por tanto, para que realmente el secreto sea tal, es necesario que
ci venga denida por una función conocida pero de la que sea computacionalmente imposible
deducir di sin el conocimiento de cierta información suplementaria que sólo posee i. Este tipo
de funciones se denominan funciones trampa y están basadas en la dicultad computacional
de ciertos problemas matemáticos. Tal y como se verá en el capítulo 4, algunos criptosistemas
de clave pública utilizan la exponenciación en un grupo multiplicativo nito como función
trampa y en su criptoanálisis es necesario resolver el problema del logaritmo discreto.

Los primeros usos conocidos de Criptograa se remontan a la antigüedad. El primero data

del siglo V a.C, durante la guerra entre Atenas y Esparta. El método utilizado es concido
como la escítala y consistía en lo siguiente. El mensaje se escribía sobre una cinta enrollada en
un rodillo de manera que, al desenrollarla, las letras quedaban descolocadas y el mensaje sólo
podía ser leído en otro rodillo de igual grosor. Asimismo se sabe que los romanos utilizaban
un cifrado consistente en sustituir unas letras por otras según una regla ja, conocida como
cifrado César. Dicha regla era trasladar la letra a cifrar unas posiciones en el alfabeto. También
aparecen textos cifrados por sustitución en la Biblia.

La obra más antigua que existe sobre Criptografía se titula Liber Zifrorum y fue escrita
por Cicco Simoneta en el siglo XV. También en este siglo, Alberti hace grandes aportaciones al
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 8

campo del criptoanálisis. En el siglo XVI el uso de la Criptografía se generalizó en los ambien-
tes diplomáticos y Vigenère reunió diversos métodos de la época en su libro Traicté des Chires.

Todos los criptosistemas utilizados hasta entonces eran muy simples pues usaban susti-
tución, transposición o una combinación de ambas cosas y, por lo tanto, fueron fáciles de
romper. En 1883, Kerckhos en su trabajo titulado La Criptografía militar [11] recomendó
que los sistemas criptográcos cumpliesen las siguientes reglas:

1. No debe existir ninguna forma de recuperar mediante un texto cifrado el mensaje original
o la clave.

2. Todo sistema criptográco debe estar compuesto por dos tipos de información:

Pública, como es la familia de algoritmos que lo denen.

Privada, como la clave que se usa en cada cifrado en particular.

3. La forma de escoger la clave ha de ser fácil de recordar y de modicar.

4. Debe ser factible la comunicación del mensaje cifrado con los medios de transmisión
habituales.

5. La complejidad del proceso de recuperación del texto original debe corresponderse con
el benecio obtenido.

Dichas reglas han sido adoptadas por gran parte de la comunidad criptográca y se resumen en
el conocido como principio de Kerckhos: la seguridad de un criptosistema se mide suponiendo
que el enemigo conoce completamente los procesos de cifrado y descifrado.

En el siglo XX se produjo un gran desarrollo en Criptografía debido a las guerras mundiales,

en las cuales era necesario establecer comunicaciones secretas a través del telégrafo y la radio.
En la Primera Guerra Mundial, el descifrado del conocido como telegrama Zimmermann, en el
que el ministro alemán pretendía convencer a Japón y México de invadir [Link], fue clave para
que [Link] entrase en guerra. Durante la Segunda Guerra Mundial, se construyó la máquina
Colossus, precursora de los ordenadores modernos. Ésta permitió a la ocina criptoanalítica
británica capitaneada por Alan Turing romper la seguridad de la máquina de cifrado alemana
Enigma.

Hasta 1976, todos los criptosistemas eran de clave privada. En ese momento, Die y
Hellman [8] establecieron los principios teóricos que debería satisfacer un criptosistema de
clave pública. Estas son las conocidas como condiciones de Die-Hellman:

1. El cálculo de las claves pública y privada debe ser computacionalmente sencillo, es decir,
dado por un algoritmo de complejidad polinómica.

2. El proceso de cifrado ha de ser computacionalmente sencillo.

3. El proceso de descifrado, conociendo la clave secreta, debe ser computacionalmente sen-

cillo.

4. La obtención de la clave secreta a partir de la pública ha de ser un problema compu-

tacionalmente imposible, es decir, dado por un algoritmo de complejidad exponencial.
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 9

5. La obtención del mensaje original, conociendo el mensaje cifrado y la clave pública, debe
ser computacionalmente imposible.

Nacieron a partir de entonces nuevos criptosistemas como el RSA o ElGamal. El prime-

ro basa su seguridad en la dicultad de factorizar un número natural compuesto. El sistema
criptográco ElGamal, por su parte, utiliza como función trampa la exponenciación modular,
cuya función inversa es el logaritmo discreto.

Los criptosistemas de clave pública tienen el defecto de ser demasiado lentos. Esta desven-
taja puede ser solventada utilizándolos únicamente para distribuir las claves para un sistema
de clave privada con el que llevar a cabo una comunicación más rápida. En esa línea, Die y
Hellman propusieron el primer protocolo de intercambio de clave basado en la exponenciación
en cuerpos nitos. Además, estos autores también introdujeron el concepto de rma digital.
La rma digital es básicamente un conjunto de datos asociados a un mensaje que permiten
asegurar la identidad del rmante y la integridad del mensaje. La rma digital debe ser:

1. Única, pudiendo generarla solamente el usuario legítimo;

2. No falsicable, el intento de falsicación debe llevar asociada la resolución de un problema

numérico intratable;

3. Fácil de autenticar, esto es, cualquier receptor puede establecer su autenticidad;

4. Irrevocable, el autor de una rma no puede negar su autoría;

5. Fácil de generar.

Otra característica que deben tener las rmas digitales es que deben depender tanto del men-
saje como del autor. Si esto no fuese así, el receptor podría modicar el mensaje y mantener
la rma, produciendo así un fraude. Los criptosistemas de clave pública pueden ser fácilmen-
te utilizados para generar rmas digitales. Un cierto usuario i con clave (ci ,di ) procede de
la siguiente manera para rmar sus mensajes. A cada mensaje M ∈ M, le asocia la rma
s = di (M ). Entonces, cualquier usuario puede calcular ci (s) y vericar que coincide con m.
Sin embargo, sólo i puede deducir el valor de s para el que ci (s) = m, esto es, sólo i puede cal-
cular la rma. En el capítulo 4 se verán algunos algoritmos de rma basados en exponenciación
que basan sus seguridad en el problema del logaritmo discreto.
Capítulo 3

Preliminares algebraicos
En este capítulo se presentan aquellas deniciones y resultados matemáticos básicos que
aparecerán con frecuencia a lo largo del trabajo.

El problema del logaritmo discreto será planteado y resuelto en grupos cíclicos nitos por
lo que conviene tener claros todos los conceptos relacionados con estas estructuras algebraicas.
Salvo que se especique otra cosa, se trabajará con grupos multiplicativos.

Denición 3.1. Sea G un grupo y sea a un elemento de G. El orden de a, ordG (a), es el

menor entero positivo r tal que ar = 1. Si ar = 1 implica r = 0, entonces se dice que a tiene
orden innito.
Si G es un grupo nito, no hay elementos de orden innito. En tal caso se tiene también
que a
|G| =1 para todo elemento a de G.
Proposición 3.2. Sea a un elemento de G de orden r. Entonces:
1. El grupo generado por a es < a >= {1, a, a2 , ..., ar−1 }.
2. Si t es un entero tal que at = 1 se cumple que r | t.
3. Si an = am para ciertos enteros n, m se tiene que n ≡ m (mód r).
Denición 3.3. Un grupo G es cíclico si existe algún elemento a ∈ G tal que G =< a >.
Corolario 3.4. Un grupo nito G es cíclico si y sólo si existe un elemento a ∈ G tal que
O(a) =| G |.
Proposición 3.5. Sea G un grupo nito de orden n.
1. El orden de cada subgrupo de G y el orden de cada elemento de G es divisor de n.
2. Si n es primo, G es cíclico y no posee subgrupos propios.
3. Si G es cíclico, para cada divisor positivo d de n existe un único subgrupo de orden d de
G.
A continuación se presentan un teorema de estructura para grupos abelianos nitos.

Teorema 3.6. Todo grupo abeliano nito G 6= ∅ es isomorfo a un producto de grupos cíclicos
nitos de órdenes m1 , ..., mt donde los mi son mayores que 1 y primos entre sí.
G ≈ Z/m1 Z × ... × Z/mt Z

10
CAPÍTULO 3. PRELIMINARES ALGEBRAICOS 11

Este isomorsmo puede calcularse mediante el teorema chino de los restos:

Teorema 3.7 (Teorema chino de los restos) .

Sean m1 , m2 , ..., mr enteros positivos dos a dos
primos entre sí. Sean a1 , a2 , ..., ar enteros cualesquiera. En esas condiciones, el sistema de
congruencias

x ≡ a1 (mód m1 )
x ≡ a2 (mód m2 )
..
.
x ≡ ar (mód mr )

tiene solución. Además, existe un único valor de x satisfaciendo todas las congruencias y
vericando que 0 ≤ x < m donde m = m1 · m2 · ... · mr .
El grupo Z/mZ es un grupo nito con la suma. El conjunto de las unidades de Z/mZ,
(Z/mZ)∗ , es un grupo de cardinal ϕ(m) donde ϕ es la función de Euler. Por lo tanto, para cada
∗
elemento a de (Z/mZ) , a
ϕ(m) = 1 (mód m). Dicho resultado es el conocido teorema de Euler.

Se utilizará también la versión para polinomios del teorema chino de los restos.

Teorema 3.8. Sea f (x) = m i=1 p1 (x)p2 (x)...pm (x) un polinomio cuyos factores pi (x) sean
Q
primos entre sí dos a dos. La aplicación
Fq [x] Fq [x] Fq [x]
ϕ: −→ ⊕ ... ⊕
(f (x)) (p1 (x)) (pm (x))
g(x) 7−→ (g1 (x), ..., gm (x))

donde gi (x) ≡ g(x) (mód pi (x)) para i = 1, ..., m, es un isomorsmo de anillos.

Por otra parte, en muchas ocasiones se trabajará en cuerpos nitos y se necesitará calcular
el logaritmo discreto en el grupo multiplicativo del cuerpo. De ahí, que el siguiente resultado
sea fundamental:

Proposición 3.9. El grupo multiplicativo de un cuerpo nito es cíclico.

El grupo multiplicativo de un cuerpo K se denota por K∗ y se denomina elemento primi-
tivo o generador,g , a cualquier elemento que lo genere. No existe un único elemento primitivo
y si g es un generador, necesariamente su orden coincide con el orden del cuerpo.

También conviene tener presente la denición y propiedades de la característica de un

cuerpo:

Denición 3.10. La característica de un cuerpo K, char(K), es el menor entero positivo r

tal que r · 1 = 0. Si la relación r · 1 = 0 implica r = 0, entonces char(K) = 0.
Proposición 3.11. La caracterísitica de un cuerpo es siempre cero o un número primo.
Proposición 3.12. Sea K un cuerpo nito. Entonces char(K) es un primo p y |K| = pm
para algún entero m ≥ 1.
Por lo tanto, si |K| = pm , el orden de K∗ es ϕ(pm ) = (p − 1)pm−1 .

Finalmente, es importante presentar la clasicación de cuerpos nitos:

CAPÍTULO 3. PRELIMINARES ALGEBRAICOS 12

Proposición 3.13. Para cada primo p y cada entero positivo m, existe un cuerpo con pm
elementos y dos cuerpos con pm elementos son isomorfos.

Como consecuencia de los últimos resultados se tiene:

1. Dado un primo p, los enteros módulo p forman un cuerpo de p elementos y, por la

proposición 3.13, todo cuerpo de p elementos es isomorfo a él. El único cuerpo (salvo
isomorsmo) de p elementos es denotado por Fp .

2. Sea q = pm , esto es, q es una potencia de un primo p. En este caso, dado un polinomio
irreducible cualquiera f (x) de grado m,
Fp [X]/f (x) es un cuerpo de q
se tiene que
elementos. Por tanto, por la proposición 3.13 todo cuerpo de q elementos es isomorfo a
él. El único cuerpo (salvo isomorsmo) de q elementos se denota por Fq .

3. Por la proposición 3.12, Fp y Fq son los únicos cuerpos nitos (salvo isomorsmo).
Capítulo 4

El problema del logaritmo discreto y

criptosistemas basados en él

4.1. El problema del logaritmo discreto

Sea G un grupo abeliano nito y sea g∈G de orden n. Dado a ∈< g >⊆ G, se dene el
logaritmo discreto de a en base g como el entero k , 0 ≤ k ≤ n − 1, tal que:

gk = a

Se dice también que k es el índice de a en base g.

El problema del logaritmo discreto (PLD) consiste en, dados g y a, calcular k.

Ejemplo 4.1. F∗2131 el grupo multiplicativo de los enteros módulo 2131.

Sea Se tiene que
F∗2131 =< 37 >. Como 1217 ≡ 375 (mód 2131), el logaritmo discreto de 1217 en base 37 es 5.

La importancia del estudio de este problema radica en el interés del logaritmo discreto
como operación inversa a la exponenciación en un grupo. La exponenciación modular es una
operación sencilla y se conocen métodos ecientes de calcularla como el que se expone a conti-
nuación. En cambio, el cálculo del logaritmo discreto módulo un entero cualquiera no siempre
puede realizarse de forma eciente.

Supóngase que se desea calcular be en el grupo multiplicativo de los enteros módulo

Pn−1 m. En
e= i
primer lugar, hay que escribir el exponente en binario: i=0 ai 2 . A continuación, han de
seguirse los siguientes pasos:

Se dene i := n − 1 y v := 1.

Para i = n − 1 hasta 0

v = vb (mód m) si ai = 1
1. v=
v=v si ai 6= 1

v=v si i=0
2. v=
v = v 2 (mód m) si i 6= 0
Tras la última iteración se tiene v = b.

13
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 14

Ejemplo 4.2. Sea F5 ∗ el grupo multiplicativo de los enteros módulo 5. Se quiere calcular 327 .
Esto puede hacerse de cualquiera de las formas explicadas:

Realizando las 26 multiplicaciones: 327 ≡ 2 (mód 5)

Utilizando el método binario de exponenciación modular. Como 27 = 24 + 23 + 2 + 1, la
representación en binario de 27 es 11011. Entonces, se toma i = 4, v = 1 y siguiendo los
pasos indicados:

i ai v
4 1 (1 · 3)2 ≡ 4 (mód 5)
3 1 (4 · 3)2 ≡ 4 (mód 5)
2 0 42 ≡ 1 (mód 5)
1 1 (1 · 3)2 ≡ 4 (mód 5)
0 1 4 · 3 ≡ 2 (mód 5)

Por lo tanto, 327 ≡ 2 (mód 5). Con este método, el número necesario de multiplicaciones
pasa de 26 a 8.

Esto pone de maniesto que la exponenciación podría ser una buena función trampa.
Precisamente, este es el motivo por el que algunos criptosistemas y sistemas de autenticación
de mensajes e intercambio de claves basan su seguridad en el PLD. En la siguiente sección se
estudian algunos de ellos.

4.2. Criptosistemas basados en el logaritmo discreto

4.2.1. Intercambio de claves de Die-Hellman (DH)

En 1976, Whiteld Die y Martin Hellman [8] propusieron el primer protocolo de in-
tercambio de clave basado en la exponenciación en cuerpos nitos. El proceso se detalla a
continuación. En primer lugar, se eligen y hacen públicos un cuerpo nito Fq y un elemento
primitivo g ∈ Fq . Supóngase que dos personas Alicia (A) y Benito (B) quieren acordar una
clave secreta común. Entonces proceden de la siguiente manera:

1. A y B eligen dos enteros, a y b respectivamente, con la única condición de que 2 ≤ a, b ≤

q−2 y los mantienen en secreto.

2. A transmite ga a B y B transmite gb a A.

3. A calcula (g b )a y B calcula (g a )b .
La clave común será entonces g ab .
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 15

Obsérvese que en la elección de a y b no se consideran los enteros 1 y q−1 ya que, en

ambos casos, el algoritmo pierde toda su seguridad.

Si a = 1 (o b = 1), entonces g a = g (o g b = g ). Por lo tanto, si se sabe que g a = g y

1 ≤ a, b ≤ q − 1, es fácil deducir que a = 1 y que la clave compartida será g b .

Si a = q − 1 (o b = q − 1), entonces g a = 1 (o g b = 1). Por lo tanto, si se sabe que

ga = 1 y que 1 ≤ a, b ≤ q − 1, es fácil deducir que a = q − 1 y hallar la clave compartida
g = (g b )q−1 .
ab

Ejemplo 4.3. Alicia y Benito quieren establecer una clave común utilizando el método de
intercambio de claves de Die-Hellman. Trabajan en el cuerpo F∗23 y toman 5 como elemento
primitivo. Entonces Alicia, elige un entero a = 7 y Benito, otro b = 13. Alicia envía a Benito
5a ≡ 17 (mód 23) y él le envía a ella 5b ≡ 21 (mód 23). A continuación, Alicia calcula 217 y
13
Benito, 17 . Ambos obtienen la clave común 5
7·13 ≡ 10 (mód 23).

Es obvio que si se dispusiese de un método ecaz para computar el logaritmo discreto,

este procedimiento perdería toda seguridad. Cualquier persona que interceptase ga y gb po-
dría obtener el entero a ab
(o b) y después hallar g , es decir, la clave común. Los autores del
protocolo conjeturaron que romper este proceso es equivalente en dicultad al problema del
logaritmo discreto pero aún no se ha demostrado. No se ha determinado si existen o no otras
formas de calcular g ab a partir de ga y g b , lo que se conoce como el problema de Die-Hellman
(PDH). El estudio de estas cuestiones ha dado lugar a variantes del DHP como el problema de
decisión de Die-Hellman, consistente en, dados g a , g b y un elemento s ∈ Fq , decidir si s = g ab .

A pesar de que no se ha demostrado que PDH y PLD son equivalentes en el caso general,
existen resultados que prueban la equivalencia de ambos problemas bajo ciertas condiciones.
Den Boer [4] probó la equivalencia en grupos Fp ∗ donde p es un primo tal que ϕ(p − 1) tiene
únicamente factores primos menores que un cierto valor. Por su parte, Maurer [14] demostró
Qr ei
la equivalencia en grupos cíclicos de orden i=1 pi si para cada primo pi se puede determinar
una curva elíptica en Fp i con ciertas propiedades cuyo orden sólo tenga divisores menores que
una cierta cota.

En 1984, Varadharajan, Odoni y Sanders [20] idearon una variante del algoritmo de Die-
Hellman utilizando la matriz compañera B de un polinomio irreducible de grado m sobre Fp .
El algoritmo consiste en los mismos pasos que el DH pero se trabaja con la matriz B en lugar
de con el elemento primitivo. Sin embargo, este nuevo procedimiento no aporta mayor segu-
ridad [21]. Incluso si la matriz B se obtuviese a partir de matrices compañeras de polinomios
irreducibles de grados m1 , ..., ms el problema podría reducirse a calcular logaritmos discretos
en los cuerpos GF (pmi ).

4.2.2. Criptosistema de Massey-Omura

Este criptosistema de clave pública fue propuesto en 1982 por James Massey y Jim K. Omu-
ra [13] como caso particular del protoloco de tres pasos ideado por Adi Shamir alrededor de
1980. En dicho protocolo, se utiliza la conmutatividad de ciertas funciones para conseguir, en
tres pasos, que dos personas intercambien un mensaje de forma segura sin compartir ninguna
clave. El proceso es el siguiente:
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 16

Paso 1: El emisor del mensaje m, A, elige una clave de cifrado eA y su correspondiente

clave de descifrado dA y envía el mensaje cifrado E(eA , m) al receptor.

Paso 2: El receptor, B, elige una clave de cifrado eB y su correspondiente clave de des-

cifrado dB . A continuación, cifra el mensaje que ha recibido E(eB , E(eA , m)) y se lo envía a A.

Paso 3: A descifra el mensaje recibido con su clave dA y envía el resultado a B. Nótese que
D(dA , E(eB , E(eA , m))) = E(eB , m) porque la función de cifrado es conmutativa.

Finalmente, B obtiene el mensaje usando su clave de descifrado: D(dB , E(eB , m)) = m.

Se presenta ahora el criptosistema de Massey-Omura. El cuerpo en el que se trabaja, Fq ,

es conocido.

Imagínese que un emisor A quiere enviar un mensaje m ∈ Fq ∗ al receptor B. En primer

lugar, A elige un entero c tal que 1 ≤ c ≤ q − 1 con c y q − 1 primos entre sí y calcula
c−1 (mód q − 1). B realiza el mismo proceso, es decir, escoge un entero d con las mismas
características que c y calcula d
−1 (mód q − 1). A continuación, A y B comienzan el siguiente

intercambio de mensajes cifrados:

1. A calcula x ≡ mc (mód q) y se lo transmite a B.

2. B calcula y ≡ xd ≡ (mc )d (mód q) y se lo envía a A.

−1 −1
3. A calcula z ≡ yc (mód q) y se lo transmite a B. (Nótese que z ≡ mcdc ≡ md
(mód q))
−1
4. B nalmente calcula zd ≡ m (mód q).

Claramente, cualquier criptoanalista capaz de resolver el logaritmo discreto podría obtener

el mensaje a partir de x = mc , y = mcd y z = md :
1. Calcula d resolviendo mcd ≡ xd (mód q) (el logaritmo discreto de mcd en base x) y c
resolviendo m
cd ≡ zc (mód q) (el logaritmo discreto de mcd en base z ).
2. Como dispone de c y d, calcula c−1 y d−1 (mód q − 1).
−1 d−1
3. m ≡ yc (mód q).
En [24], Sakurai y Shizuya probaron que, en F∗p donde p es un primo tal que p−1 tiene
sólo factores primos pequeños con respecto a una cierta cota, si se conoce la factorización de
p−1 y g es un generador de F∗p , el PLD es equivalente a romper la seguridad del criptosistema
Massey-Omura.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 17

Ejemplo 4.4. Alicia quiere enviar a Benito el mensaje m = 13 en F∗53 utilizando el criptosis-
tema de Massey-Omura. Para ello, Alicia elige c=3 y calcula c
−1 = 35. Benito escoge d = 7

y obtiene d
−1 = 15. Entonces, comienzan el intercambio de mensajes cifrados:

1. Alicia envía 133 ≡ 24 (mód 53).

2. Benito calcula 247 ≡ 36 (mód 53) y se lo envía a Alicia.

3. Alicia envía a Benito 3635 ≡ 15 (mód 53).

4. Benito obtiene el mensaje m calculando 1515 ≡ 13 (mód 53).

4.2.3. Criptosistema de ElGamal

Este criptosistema fue propuesto por Taher ElGamal [9] en 1985. Se conocen el cuerpo Fq
y un elemento primitivo g del mismo.

Cierto usuario del sistema, A, elige un entero a tal que 2 ≤ a ≤ q − 2 y calcula g a . El entero
a a
es su clave privada y g es la clave pública. Si otro usuario, B, quiere mandar un mensaje
m a A ha de hacer lo siguiente:

1. Elegir un entero k, 2 ≤ k ≤ q − 2

2. Enviar el par (g k , mg ak ) a A.

Nota: en la elección de a y k, los enteros 1 y q−1 se descartan por razones similares a las
expuestas en el intercambio de claves de Die-Hellman (ver apartado 4.2.1).

A partir del par (g k , mg ak ), es fácil para A obtener el mensaje original m de la siguiente

manera:

1. Calcula g ak = (g k )a

2. Halla (mg ak )/g ak = m

El segundo paso para recuperar el mensaje puede ser sustituido por:

1. Calcula (g k )q−1−a

2. Halla (g k )q−1−a mg ak = mg k(q−1)−ka+ak = m(g q−1 )k = m

Este método es más eciente que el anterior puesto que evita calcular el inverso de g ak .
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 18

Ejemplo 4.5. Alicia y Benito quieren intercambiar mensajes utilizando el criptosistema de El-
Gamal en el cuerpo F157 g = 5. Para ello, Alicia escoge su clave privada a = 25 y
con generador
comparte su clave pública g
a = 34. Supongamos que Benito quiere mandar el mensaje m = 19
89
a Alicia. Entonces elige un entero k = 89 y le envía el par (5 , 19 · 5
25·89 ) = (131, 45). Para ob-

tener el mensaje original, Alicia halla 5

25·89 ≡ 85 (mód 157) y calcula 45/85 ≡ 19 (mód 157).

Alicia también puede recuperar el mensaje a partir de 5

89(157−1−25) ≡ 133 (mód 157) y calcu-

lando 133 · 45 ≡ 19 (mód 157).

Es importante señalar que el usuario B, debe elegir un entero k distinto para cada mensaje
que quiera enviar a A. Supóngase que B utiliza el mismo k para codicar dos mensajes diferen-
tes,m1 y m2 . Esto es, B envía (g k , m1 g ak ) y (g k , m2 g ak ) a A. Entonces, cualquier criptoanalista
que sepa de esta debilidad por parte de B y conozca el mensaje original m1 correspondiente
k ak
al mensaje cifrado (g , m1 g ) puede calcular fácilmente la clave común m1 g /m1 = g
ak ak y

proceder de la misma manera que si fuese A para obtener m2 .

Obviamente, cualquier persona capaz de resolver el PLD podría obtener a (o k) y estar

en las mismas condiciones que el usuario A para obtener el mensaje original. Tsiounis y Yung
[7] demostraron que la seguridad de ElGamal es equivalente al problema de decisión de Die-
Hellman. Además, Sakurai y Shizuya [24] probaron que, en F∗p donde p es un primo tal que
p − 1 tiene sólo factores primos pequeños con respecto a una cierta cota, dada la factorización
∗
de p − 1 y si g es un generador de Fp , la seguridad de este criptosistema es equivalente al PLD.

4.2.4. Algoritmo de rma de ElGamal

ElGamal [9] también propuso un algoritmo de rma basado en exponenciación en cuerpos

nitos Fp con p primo. Imagínese que uno de los participantes, A, quiere rmar los mensajes.
Para ello A publica un primo p, un elemento primitivo g módulo p y un entero y , 1 ≤ y ≤ p−1,
tal que y= g a donde a es un entero cualquiera que mantiene en secreto. El primo p y g pueden
ser elegidas por cada usuario o ser las mismas para todos los participantes.

Para rmar un mensaje m, A procede así:

1. Elige un entero k con (k, p − 1) = 1 y calcula r = gk .

2. Calcula s a partir de la ecuación: m ≡ ar + ks (mod p − 1) (que tiene solución única

puesto que (k, p − 1) = 1)
La rma de A para el mensaje m es, por lo tanto, el par (r, s).

Obviamente, si alguien fuese capaz de calcular logaritmos discretos y obtener el entero a a

partir de y, podría rmar mensajes como si fuese el usuario A. Es más, no se ha encontrado
ninguna forma de romper la seguridad de este sistema de rma sin utilizar logaritmos discretos.

Si un usuario quiere vericar que un mensaje m procede efectivamente de A, debe vericar

si:

g m ≡ y r rs (mod p)
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 19

ya que, si efectivamente A es el emisor:

y r rs ≡ g ar g ks ≡ g ar+ks ≡ g m (mod p)

Ejemplo 4.6. Cierto usuario toma como clave privada a = 33 y comparte la siguiente clave
pública: (151, 6, 60). Si el usuario quiere rmar el mensaje m = 79 debe proceder como sigue:

1. Elige un cierto k, por ejemplo, k = 11 y calcula r ≡ 611 ≡ 77 (mód 151)

2. Calcula s ≡ (79 − 33 · 77)/11 ≡ 8 (mód 150)

La rma del mensaje m = 79 es (77, 8). Si el destinatario del mensaje quiere vericar la autoría
del mismo, ha de comprobar que 679 ≡ 63 ≡ 6077 · 778 (mód 151).

4.2.5. Algoritmo de rma digital (DSA)

DSA es un estándar del Gobierno Federal de los Estados Unidos de América para rmas
digitales. Fue propuesto por el NIST (National Institute of Standards and Technology) [17]
en 1994 y el esquema de pasos a seguir para rmar un mensaje es similar al del algoritmo de
rma ElGamal.

Con este algoritmo, si un usuario A quiere rmar un mensaje lo primero que debe hacer
es establecer la clave pública (p, q, g, y) y la privada x. Para elegir dichas claves, ha de seguir
las siguientes instrucciones
1

1. Eligir un primo, p, de tamaño L, donde 512 ≤ L ≤ 1024 y 64 | L.

2. Escoger otro primo, q, de tamaño 160, tal que p ≡ 1 (mód q).

3. Sea h un entero tal que 1 < h < p − 1 y h(p−1)/q 6= 1 (mód p). Tomar g ≡ h(p−1)/q
(mód p). Las condiciones impuestas sobre h garantizan que g es un generador del único
∗
subgrupo cíclico de orden q de Fp . Como g ≡ h
q p−1 ≡ 1 (mód p), el orden de g es divisor

de q , esto es, 1 o q , pero no puede ser 1 ya que g 6= 1. Entonces el orden de g es q y, por

lo tanto, genera el único subgrupo de orden q de Fp .
∗

4. Escoger x tal que 1 < x < q − 1.

5. Calcular y ≡ g x (mod p)

El usuario A está ahora en disposición de rmar su mensaje m. Debe obtener un par de enteros
(r, s) a través de los siguientes cálculos:

1. Elige un entero k vericando 0 < k < q.

2. Obtiene r ≡ (g k (mód p)) (mód q)

3. Calcula s ≡ k −1 (H(m) + xr) (mód q), donde H es la función hash SHA-1. .

2

Si el receptor del mensaje rmado quisiera asegurarse de que este ha sido realmente enviado
por A, debería realizar los siguientes cálculos:

1
Las condiciones de tamaño para los enteros p y q de los pasos 1 y 2, respectivamente, no tienen justicación
matemática, sino que responden a cuestiones computacionales.
2
Una función hash es una aplicación h : Σ∗ −→ Σn , n ∈ N que transforma una cadena de longitud arbitraria
en una de longitud ja. Dicha aplicación debe cumplir además ciertas características adicionales [27]
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 20

1. w = s−1 (mód q)

2. u1 = H(m)w (mód q)

3. u2 = rw (mód q)

4. Finalmente, verica si g u1 y u2 ≡ r (mód p).

Efectivamente, si A es el rmante, se tiene:

g q ≡ h(p−1) ≡ 1 (mód p)

k ≡ H(m)s−1 + xrs−1 ≡ H(m)w + xrw (mod q)

Por tanto,

g k ≡ g H(m)w+xrw+zq ≡ g H(m)w g xrw g qz ≡ g u1 y u2 (mód p)

Al igual que en el algoritmo de rma de ElGamal, cualquier persona capaz de calcular
logaritmos discretos podría calcular x y hacerse pasar por el usuario A.

4.2.6. Algoritmo de Blum-Micali

El algoritmo de Blum-Micali [3] es un generador de números pseudoaleatorios que basa su

seguridad en la dicultad de calcular logaritmos discretos. Las secuencias de números pseudo-
aleatorios tienen aplicación en múltiples campos tales como la Criptografía, la simulación y la
Estadística.
Sea p un primo impar y sea g un elemento primitivo módulo p. Dado un valor inicial x0 ,
se dene la sucesión:

xi+1 ≡ g xi (mod p)
A partir de xi se genera el bit pseudoaleatorio:

1 si xi ≤ (p − 1)/2
yi =
0 en otro caso

Esto es, yi = 1 cuando xi es la raíz principal de x2i módulo p, teniendo en cuenta que, dado un
2
residuo cuadrático T = g
2s módulo p, se dice que g s con s ∈ [1, (p − 1)/2] es la raíz principal

de T y que g
s+(p−1)/2 es la raíz no principal.

Denida de esta forma, se tiene que {yi }ki=1 es una secuencia pseudoaleatoria de k bits.

En [3], Blum y Micali demostraron que cualquier estrategia eciente para predecir la se-
cuencia puede ser transformada en una estrategia igualmente eciente para resolver el PLD.
Esto se debe a que disponer de un oráculo para la raíz principal permite construir un algo-
ritmo que resuelva el PLD módulo p. Sin embargo, dicho problema es intratable para primos
sucientemente grandes y, por lo tanto, la seguridad del algoritmo de Blum-Micali reside en
la dcultad del PLD.

Ejemplo 4.7. Sea p = 67 y g = 2. Dado x0 = 3 y k = 15, empleando el algoritmo de

Blum-Micali se obtiene la siguiente secuencia pseudoaleatoria de 15 bits:

101111100100000
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 21

4.2.7. Criptosistema de Ciss-Cheikh-Sow

En [7], Ciss, Cheikh y Sow proponen un criptosistema de clave pública cuya seguridad se
basa en los problemas de factorización y logaritmo discreto.

Cada usuario debe generar sus claves pública y privada, procediendo de la siguiente manera:

1. Elige dos primos p y q congruentes con 2 (mód 3) y calcula pq = n.

2. Toma g un elemento primitivo de Zn .

3. Toma un k < ϕ(n) y calcula y ≡ g k (mód n)

La clave privada de este usuario, A, es (p, q, k) y la pública,(n, g, y)

Si otro usuario, B, quiere mandar un mensaje m a A debe seguir los siguientes pasos:

1. Elige un entero s<n

2. Calcula c1 ≡ (my s )3 (mód n) y c2 ≡ g s (mód n)

B envía el par (c1 , c2 ) a A.

Para descifrar el mensaje, A calcula:

(c1 )1/3 (c2 )−k ≡ (mg ks )g −ks ≡ m (mód n)

Es importante notar que A puede calcular la raíz cúbica de c1 (mód n) (y es única) porque
la ecuación x
3 ≡ c1 tiene solución única módulo p y módulo q. Esto último se debe a que, si
p es un primo tal que p ≡ 2 (mód 3), entonces la función:

Zp −→ Zp
x 7−→ x3

es biyectiva con inversa:

Zp −→ Zp
x 7−→ x1/3 ≡ x(2p−1)/3

La seguridad del algoritmo recae tanto en la factorización de n como en el PLD. Si un

criptoanalista es capaz de factorizar n, puede obtener (c1 )1/3 ≡ my s (mód n) resolviendo la
raíz cúbica módulo p y módulo q y utilizando el teorema chino de los restos. Sin embargo,
también necesita obtener s, esto es, necesita calcular el logaritmo discreto de c2 en base g
s
módulo n, para poder calcular y y despejar m en la ecuación anterior. Por otra parte, si
el criptoanalista es capaz de calcular logaritmos discretos, entonces, puede obtener la clave
privada k y calcular c2 ≡ y ks (mód n). No obstante, también necesita calcular (c1 )1/3 ≡ my ks
(mód n) (para después hallar m) y para calcular esta raíz cúbica, es necesario conocer la
factorización de n. Por lo tanto, queda probado que saber resolver uno de los dos problemas
no permite obtener el mensaje original y que, en consecuencia, la seguridad del criptosistema
se basa tanto en la factorización de n como en el PLD.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 22

Ejemplo 4.8. Cierto usuario, Alicia, eligep = 113 y q = 353 y calcula n = 39889. A
continuación toma un elemento primitivo de Z39889 , g = 3. Elige k = 145 y calcula y ≡
3 145 ≡ 29125 (mód 39889). La clave privada de Alicia es (113, 353, 145) y la clave pública,
(39889, 3, 29125). Si Benito quiere enviarle un mensaje, por ejemplo, m = 3168 debe hacer lo
siguiente:

1. Elige s = 5671

2. Calcula c1 ≡ (3168 · 291255671 )3 ≡ 4914 (mód 39889) y c2 ≡ 35671 ≡ 38253 (mód 39889)

Benito envía el par (4914, 38253) a Alicia. Esta, para recuperar el mensaje calcula:

49141/3 · 38253−145 ≡ 3168 (mód 39889)

Para hallar 49141/3 (mód 39889) Alicia calcula 49141/3 ≡ 4914(2·113−1)/2 ≡ 54 (mód 113) y
49141/3 ≡ 4914(2·353−1)/2 ≡ 264 (mód 353) y utiliza el teorema chino de los restos.
Capítulo 5

Métodos de cálculo del logaritmo

discreto
Hasta ahora se han presentado algunas de las aplicaciones del logaritmo discreto en Crip-
tografía. Un método ecaz para resolver el PLD pondría en jaque la seguridad de todos los
sistemas basados en él que son utilizados hoy en día. En este capítulo se estudian algunos
de los algoritmos existentes para el cálculo del logaritmo discreto: Dichos algoritmos pueden
clasicarse en tres tipos:

1. Algoritmos genéricos, esto es, algoritmos válidos en cualquier grupo.

2. Algoritmos para grupos cuyo cardinal tiene todos sus factores primos pequeños.

3. Algoritmos que utilizan propiedades particulares del grupo (en cuanto a su estructura).

En lo que sigue, salvo que se especique otra cosa, se trabajará en un grupo cíclico
G =< g > de orden n y el objetivo será calcular el logaritmo discreto de a ∈ G en base
g , esto es, calcular k tal que g
k = a.

5.1. Algoritmos Genéricos

5.1.1. Fuerza Bruta

La manera más obvia de calcular el logaritmo discreto de un elemento a en base g es

calcular las diferentes potencias de g, almacenarlas en una tabla y buscar el elemento k en
dicha tabla. Claramente este método no es ecaz cuando el orden del grupo es grande.

Ejemplo 5.1. Se desea calcular en F∗97 el logaritmo discreto de 36 en base 5. Para ello, se
construye la tabla de las sucesivas potencias de 5:

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
5j 1 5 25 28 43 21 8 40 6 30 53 71 64 29 48 46 36

Por lo tanto, 36 ≡ 516 (mód 97). Esto es, el logaritmo discreto de 36 en base 5 es 16.

23
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 24

5.1.2. Algoritmo de Shanks: Baby step-Giant step

Obviamente la fuerza bruta no es un buen método para calcular logaritmos discretos puesto
que sólo es eciente en grupos de orden pequeño. El método que se introduce en este apartado
puede aplicarse de manera ecaz a un mayor número de grupos.

Todo elemento a de un grupo G de orden n puede ser expresado de manera única como
√
a = g k donde k es un entero no negativo menor que n − 1. Sea m = d n e (la parte entera
√
de n por arriba), entonces, todo k puede expresarse como k = mq + r con 0 ≤ q, r ≤ m − 1,
simplemente escribiendo k en base m. Este hecho es la base del método de Shanks [25].

El método de Shanks para calcular el logaritmo discreto de a en base g consiste en los

siguientes pasos:

1. Calcular los conjuntos:

Baby Steps : {ag −i : 0 ≤ i ≤ m − 1} = {a, ag −1 , ag −2 , ... , ag −(m−1) }
Giant Steps : {g jm : 0 ≤ j ≤ m − 1} = {1, g m , g 2m , ... , g (m−1)m }

2. Buscar en esos conjuntos elementos que tengan el mismo valor. Es decir, buscar un
elemento ag −i en el primer conjunto y otro elemento g jm en el segundo tales que ag −i =
g jm .

3. Despejando a, se tiene que: a = g jm+i y, por lo tanto, el logaritmo discreto de a en base

g es k = jm + i.

Nótese, atendiendo a las consideraciones iniciales que los elementos buscados en el paso 2
existen por la manera en que se han denido los conjuntos. De hecho, puede existir más de
un par de elementos vericando la condición requerida y las soluciones obtenidas al considerar
los distintos pares dieren en un múltiplo de n. Además, el método también proporciona la
solución del PLD si n es una cota superior del orden del grupo.

Ejemplo 5.2. Se quiere calcular el logaritmo discreto de a = 59 en base g=7 en el grupo

F71 ∗ mediante el método de Shanks:

√
m = d 70e = 9
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 25

Baby Steps Giant Steps

i 59 · 7−i j 79j
0 59 0 1
1 49 1 47
2 7 2 8
3 1 3 21
4 61 4 64
5 29 5 26
6 65 6 15
7 60 7 66
8 39 8 49

Se observa que 1 ≡ 59 · 7−3 ≡ 70 (mód 71). 59 ≡ 73 (mód 71), esto es, el

Entonces,
logaritmo discreto de 59 en base 7 es 3. También se tiene que 59·7
−1 ≡ 78·9 (mód 71), es decir,
73
59 ≡ 7 (mód 71) pero 73 ≡ 3 (mód ϕ(71)) y, por lo tanto, se obtiene la misma solución. En
la segunda tabla se podrían haber omitido los cálculos para j mayor que 0, en cambio, estos
se han realizado para comprobar que, efectivamente, pueden existir varias colisiones.

5.1.3. Algoritmo ρ de Pollard

El método ρ de Pollard [23] consiste en construir una secuencia pseudoaleatoria de ele-

mentos de G en la que existan dos términos iguales y, a partir de esos términos, calcular el
logaritmo discreto. Se trata del algoritmo genérico más ecaz y, por ello, además de estudiar
el método original, se presentan algunas variantes del mismo. A continuación se expone el
método original en detalle.

En primer lugar, se toma una partición de G en tres conjuntos de aproximadamente el

mismo tamaño S1 , S2 y S3 con la única condición de que 1 no pertenezca a S2 . La secuencia
estará dada por:

xi a si xi ∈ S1
x0 = 1; xi+1 = x2i si xi ∈ S2
xi g xi ∈ S3

si

Si 1 está en S2 , entonces la secuencia es constante igual a 1. Esto explica la condición requerida

para S2 a la hora de elegir la partición de G.

Como a = gk , se tiene que xi = g αi aβi y los enteros αi y βi pueden calcularse indepen-

dientemente del valor xi de forma recurrente:

 αi si xi ∈ S1
α0 = 0; αi+1 = 2αi si xi ∈ S2
αi + 1 xi ∈ S3

si


βi + 1 si xi ∈ S1
β0 = 0; βi+1 = 2βi si xi ∈ S2
βi xi ∈ S3

si

Cuando se encuentran dos enteros i, j tales que xi = xj , se verica que:

g αi aβi = g αj aβj
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 26

esto es,
g αi g kβi = g αj g kβj
y, por lo tanto,
g αi −αj = g k(βj −βi )
de donde se obtiene que:
αi − αj ≡ k(βj − βi ) (mód n) (5.1)

Denotando u = αi − αj y v = βj − βi se tiene que g u = g kv . Es claro que, si v = 0, el

algoritmo no puede calcular el logaritmo discreto. En tal caso, se toma otra semilla, esto es,
otro valor para x0 y se repite el proceso. Si v 6= 0 se aplica el algoritmo extendido de Euclides
para resolver la ecuación (5.1). Sea d = (n, v), entonces:
d = vs + nt
Como
g us = g kvs = g k(d−nt) = g kd
se tiene que
us ≡ kd (mód n)
y por lo tanto
us − wn = kd
Puesto que d | n, d | us y, nalmente, se obtiene que:

k = (us − wn)/d
donde w es un entero entre 0 y d que puede obtenerse por búsqueda exhaustiva.

Es fácil observar que, una vez que se da xi = xj , los elementos que se generan a partir del
paso j son los mismos que los que se generan a partir del paso i y, por lo tanto, la secuencia
entra en un bucle. Dibujando la situación se obtiene una forma parecida a la letra ρ y es este
hecho el que da nombre al algoritmo.

Ejemplo 5.3. El entero p = 809 es primo y g = 89 tiene orden 101 en F∗809 . El elemento 618
pertenece al subgrupo generado por g. Se desea calcular el logaritmo en base 89 de 618 en
F∗809 . En primer lugar, se toma la siguiente partición del grupo F∗809 :

S1 = {x ∈ F∗809 : x ≡ 1 (mód 3)}

S2 = {x ∈ F∗809 :x≡0 (mód 3)}
S3 = {x ∈ F∗809 :x≡2 (mód 3)}
En este momento se genera la secuencia aleatoria aplicando la función denida en la descripción
del método y se busca una colisión en la misma.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 27

i (xi , αi , βi ) i (xi , αi , βi )
1 (618,0,1) 8 (605,4,10)
2 (76,0,2) 9 (451,5,10)
3 (46,0,3) 10 (422,5,11)
4 (113,0,4) 11 (344,6,11)
5 (349,1,4) 12 (683,7,11)
6 (488,1,5) 13 (112,8,11)
7 (555,2,5) 14 (451,8,12)

Se tiene que x9 = x14 = 451. Por tanto, el logaritmo discreto de 618 en base 89 es:

k = (8 − 5)(10 − 12)−1 = 3 · 99−1 = 3 · 50 = 49 (mód 101)

Variantes del algoritmo

En este apartado se necesita la siguiente denición:

Denición 5.4. Decimos que en una secuencia, {xi }i∈N , existe un ciclo de longitud λ si existe
µ tal que para todo índice i mayor o igual que µ se tiene que xi = xi+λ . En tal caso, se verica
también que xi = xi+kλ para todo entero k no negativo.
Nótese, que en el método de Pollard no se requiere encontrar los valores de λ y µ, basta
con hallar dos elementos iguales de la secuencia.

En lo que sigue, siempre que no se diga nada, se considerará que λ y µ son los menores
enteros positivos vericando las condiciones de la denición de ciclo. Conviene comentar que
µ+λ mide el número máximo de iteraciones porque el elemento xµ+λ es el primer elemento
repetido de la secuencia. Así, cuanto menores sean ambos valores, más rápido se hallará una
colisión y, por tanto, más rápido será el método. Se introduce a continuación un resultado que
será útil para estudiar las mejoras en la ecacia de ejecución de las variantes del algorirmo de
Rho.

Teorema 5.5 (Harris [10]). Bajo la hipótesis de que una función de iteración,
p f : G → G√ , se
comporta como una función aleatoria, las esperanzas de λ y µ son la misma, πn/8 ≈ 0,63 n,
y la media del número máximo de evaluaciones necesarias antes de encontrar un colisión en la
√
secuencia generada por f es E(µ + λ) = πn/2 ≈ 1,25 n, suponiendo que se guardan todos
p

los elementos de la secuencia. (Recordemos que n = |G|)

Es importante remarcar la importancia de la hipótesis sobre la función de iteración. Teske
[29] probó empíricamente que la función iteración de Pollard no se comporta exactamente
como una función aleatoria y, por lo tanto, los resultados obtenidos son peores que los del
√
Teorema 5.5. Por ejemplo, en F∗p , donde p es primo, E(µ + λ) ≈ 1,37 n y en subgrupos de
√
orden primo de dicho grupo, E(µ + λ) ≈ 1,55 n.

Se pasan a presentar ahora diversas variantes del método ρ. En primer lugar, cabe mencio-
nar que el algoritmo original no necesita almacenar toda la secuencia para encontrar un par
de elementos iguales, sino que, basta con que se trabaje con los conjuntos:

(xi , αi , βi ; x2i , α2i , β2i ) para i = 1, 2, ...

De hecho, este es el método que Pollard utilizó cuando presentó su algoritmo.

CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 28

Teorema 5.6 (Detección de ciclos de Floyd). Si en una secuencia, {xi }i∈N , existe un
ciclo, entonces existe un número natural i tal que xi = x2i . El menor i que verica xi = x2i
cumple que µ ≤ i ≤ µ + λ, donde µ es el índice del primer elemento del ciclo y λ es la longitud
del mismo.
Demostración. Por denición de ciclo, existen λ y µ tales que para todo entero i mayor o igual
que µ se tiene que xi = xi+kλ . Por tanto, siempre que i = kλ ≥ µ se verica que xi = x2i .
Es fácil ver que el menor i que verica xi = x2i cumple que µ ≤ i ≤ µ + λ. Efectivamente, i
no puede ser menor que µ porque entonces xi no sería un elemento dentro del ciclo. Además,
si i fuese mayor que µ + λ,

xi = xµ+λ+k = xµ+k y x2i = x2(µ+λ+k) = x2(µ+k)

Entonces dicho i no sería el menor satisfaciendo la condición requerida ya que xµ+k = xµ+λ+k =
x2(µ+λ+k) = x2(µ+k) .

Ejemplo 5.7. Se considera la secuencia:

5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...

Se procede a hallar una colisión, utilizando el algoritmo de detección de ciclos de Floyd.

i 1 2 3 4 5 6 7 8 9 10
xi 5 7 8 22 33 15 46 39 11 12
x2i 7 22 15 39 12 26 22 15 39 12

Por lo tanto, x10 = x20 = 12. Obsérvese que el algoritmo no encuentra el primer elemento
repetido de la secuencia, que sería x3 = x13 = 8,sino que tan solo proporciona una colisión.

Este teorema explica que para encontrar dos elementos iguales en la sucesión de Pollard
baste con comparar entre sí los elementos xi y x2i . Además, como µ ≤ i ≤ µ+λ, para encontrar
una colisión, se necesitan µ µ + λ en el peor. Aunque el
iteraciones en el mejor de los casos y
método requiere muy poco espacio de almacenamiento, suponiendo que f se comporta como
√
una función aleatoria, el número máximo de iteraciones necesarias es aproximadamente 1,03 n
√
([2]) y, como en cada iteración hay tres evaluaciones y una comparación, se precisan 1,03 n
√
comparaciones y 3,09 n evaluaciones aproximadamente. Por tanto, la mejora de este método
reside en la disminución de almacenaje ya que el número de evaluaciones es muy superior al
del Teorema 5.5. El hecho de que en cada iteración haya tres evaluaciones se explica por lo
siguiente: como en la iteración i, tenemos calculados xi yx2i , en la iteración i + 1 necesitamos
calcular xi+1 = f (xi ), x2i+1 = f (x2i ) y x2(i+1) = x2i+2 = f (x2i+1 ).

Tal y como se ha visto en el ejemplo, el método de Floyd no proporciona necesariamente

el primer elemento repetido. Tampoco tiene porqué proporcionar la longitud del ciclo. Sin
embargo, es posible calcular λ y µ a partir de la colisión encontrada. Cuando se encuentra
i tal que xi = x2i , se obtiene un periodo ν = 2i − i = kλ que es múltiplo de la longitud
del ciclo. Una vez conocido ν, se traza la secuencia desde el primer término para encontrar
el primer valor repetido xµ sabiendo que, como λ es múltiplo de µ, xµ = xµ+ν . Esto quiere
decir, que sólo se necesita comparar los elementos xj y xj+ν hasta hallar un valor de j pa-
ra el que se verique la igualdad. Cuando ya se ha obtenido µ, es fácil hallar λ comparando
los elementos xµ y xµ+l . Entonces λ será el menor valor de l para el que se verique la igualdad.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 29

Se presentan a continuación algunas variantes del método que pueden ser agrupadas en
dos tipos: las que proponen formas diferentes para hallar elementos repetidos en la secuencia
y las que usan diferentes funciones de iteración.

En 1980, Brent [5] aumentó la velocidad del método de Rho al emplear otro algoritmo
de detección de ciclos. El algoritmo de Brent utiliza, al igual que el algoritmo de Floyd, dos
variables. Sin embargo, está basado en una idea diferente. La base de este algoritmo es que
dado un elemento del ciclo, es posible encontrar la longitud del ciclo en λ pasos (de la misma
manera en que se hallaba en el algoritmo de Floyd). Se van tomando elementos de la forma
x2j y se comprueba si están o no en el ciclo hasta que uno de ellos verica esa condición.

Se consideran las variables x2j y x2j +k . Inicialmente, estas variables toman los dos pri-
meros valores de la secuencia. Entonces, se va incrementando el valor de k en una unidad, y
comprobando en cada caso si x2j = x2j +k . Si ambas variables no coinciden para ningún valor
de k menor o igual que 2j , se actualiza j = j + 1, k = 1 y se repite el proceso. El valor de
j indica el paso en que se encuentra el proceso. El siguiente esquema pretende claricar el
proceso:

Teorema 5.8 (Detección de ciclos de Brent). Si en una secuencia {xi }i∈N existe un
ciclo de longitud λ, entonces existe un número natural j tal que x2j = x2j +λ . Además, el
algoritmo que se acaba de describir encuentra dicho valor j cuando 2j ≥ máx(µ, λ), donde µ
es el subíndice del primer elemento del ciclo.

Demostración. Por denición, como la secuencia tiene un ciclo, existen λ y µ tales que xi =
xi+λ para todo i mayor o igual que µ. Entonces, siempre que i = 2j ≥ µ se verica que
x2j = x2j +λ .
j
Se prueba ahora la segunda parte del teorema. Si 2 ≥ máx(µ, λ) es inmediato comprobar
j
que el algoritmo halla una colisión pues 2 ≥ µ, esto es, x2j es un elemento del ciclo que se
j i
compara con x2j +k donde 1 ≤ k ≤ 2 . Es decir, se compara un elemento del ciclo con 2 ≥ λ
elementos consecutivos, lo que forzosamente lleva a encontrar una colisión. Por otro lado, si
el algoritmo encuentra una colisión, x2j ha de estar en el ciclo, esto es, 2j ≥ µ, y ha de ser
comparado con, al menos, λ elementos consecutivos, es decir k≥λ y,
j
por tanto, 2 ≥ λ. Esto
quiere decir, que no puede encontrar j con 2
j < máx(λ, µ).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 30

Este algoritmo presenta dos ventajas con respecto al anterior. Aunque el espacio de alma-
cenamiento requerido tanto en el método de Floyd como en el de Brent es similar y mínimo,
el algoritmo de Brent necesita menos operaciones. El número máximo de iteraciones necesa-
√
rias es aproximadamente 1,98 n, suponiendo de f se comporta como una función aleatoria
[2], y en cada iteración hay una evaluación y una comparación. Por tanto, si el coste de las
comparaciones es insignicante, el algoritmo de Brent es más rápido que el de Floyd. Por otro
lado, Brent encuentra la longitud del ciclo, λ, directamente. Si se desease hallar µ habría que
proceder de manera análoga a como se comentó en el algoritmo de Floyd.

Ejemplo 5.9. Se va a hallar una colisión de la secuencia del ejemplo 5.7 mediante el algoritmo
de detección de ciclos de Brent.

5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...

x1 = 5 x2 = 7 x4 = 22
k 1 k 1 2 k 1 2 3 4
x1+k 7 x2+k 8 22 x4+k 33 15 46 39

x8 = 39
k 1 2 3 4 5 6 7 8
x8+k 11 12 31 26 8 22 33 15

x16 = 15
k 1 2 3 4 5 6 7 8 9 10
x16+k 46 39 11 12 31 26 8 22 33 15

El algoritmo detecta la colisión x16 = x26 = 15 y proporciona la longitud del ciclo λ = 10.
Brent mejoró dicha variante en el mismo artículo demostrando que podían evitarse com-
paraciones innecesarias. Probó que basta con comparar cada x2j con los términos x2j +k donde
3 j
2 < 2j + k ≤ 2j+1 , esto es, 2j−1 < k ≤ 2j . Es decir, en esta versión solo se considera la
2
mitad de valores posibles para k . Sea {x2j +1 , x2j +2 , ..., x 3 2j } y {x 3 2j +1 , x 3 2j +2 , ..., x2j +2j } una
2 2 2
partición de los elementos considerados en cada iteración del algoritmo original. Cada uno de
los conjuntos tiene 2j−1 elementos. Si λ ≤ 2j−1 , esto es x2j +λ está en el primer conjunto,
entonces x2j también es igual a un elemento del segundo conjunto (porque x2j +2λ pertenece a
él). Entonces, basta con buscar colisiones en el segundo conjunto, pero en este caso no siempre
se halla el valor de λ directamente. En esta variante del algoritmo, el número máximo de
√ √
evaluaciones está acotado por 2,24 n y el de comparaciones por 0,88 n.

Por otra parte, Teske [28] introdujo una variante del algoritmo que reduce el número de
iteraciones a cambio de almacenar más elementos de la secuencia y utilizar más comparaciones.
El algoritmo de Teske utiliza un vector de tamaño t, (xσ1 , ..., xσt ) con t ≥ 2, cuyas componentes
albergan inicialmente el valor de x0 y se actualizan de la siguiente manera. En la i-ésima
iteración, se compara el valor de xi con el de cada componente del vector. Si no hay ningún
valor igual, se comprueba sii es mayor o igual que v veces el índice del elemento en la primera
componente para un cierto valor de v previamente jado. Si es así, se elimina el elemento de
la primera componente, se mueve el elemento de cada componente a la anterior (xσk−1 = xσk ),
se guarda xi en la última componente (xσt = xi ) y se pasa a la siguiente iteración. Si no, el
vector no se modica y continúa con el proceso.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 31

Teorema 5.10 (Detección de ciclos de Teske). Sea {xi }i∈N una secuencia con un ciclo
de longitud λ y sean v ,t enteros positivos jos tales que vµ ≥ λ + µ donde µ es el subíndice del
primer elemento del ciclo. En estas condiciones, el algoritmo anterior encuentra una colisión.

Demostración. Como la secuencia presenta un ciclo, para todo i mayor o igual que µ se tiene
que xi = xi+λ . Además, si k ≥ µ se verica que vk ≥ λ+k . Como k ≥ µ, existe s con k = µ+s
y, por tanto,

vk = v(µ + s) = vµ + vs ≥ λ + µ + vs ≥ λ + µ + s = λ + k

Entonces, si se almacena un cierto xk con k≥µ y se compara con los sucesivos términos de
la secuencia, se garantiza que se encuentra un elemento xl con xk = xl y k < l ≤ vk , por
ejemplo, l = k + λ.
Ha de probarse entonces que en algún momento el vector contiene un elemento xk con k ≥ µ.
Es claro que el algoritmo no puede hallar ninguna colisión antes de llegar a la iteración µ.
Supóngase que en este momento se tiene el vector (xσ1 , ..., xσt ). Entonces, se ha de vericar si
µ + h ≥ vσ1 para h ≥ 0. Como vσ1 es un valor jo, la desigualdad será cierta para algún h y,
en ese momento, el vector almacenará el valor xµ+h = xk con k ≥ µ.
Sólo falta ver que el elemento xk aún está almacenado en el vector cuando se llega a la iteración
l ≤ vk . Si no fuese así, habría sido eliminado en cierta iteración j < l. Esto quiere decir que
j vericaría j ≥ vk pero se tenía que j < l ≤ vk y, por lo tanto, xk aún está en el vector al
llegar a la iteración l.

Una cuestión delicada es la elección de los parámetros v y t. Cuanto mayor sea t, mayor
espacio de almacenamiento y más comparaciones son necesarios. En [28] también se muestra
que σi+1 ≈ Rσi para algún R y que cuanto mayor es v mayor es R y, por tanto, más iteraciones
son necesarias entre una sustitución del primer término y la siguiente. Por otro lado, para
hallar una colisión ha de darse que σi ≥ µ y σi + λ ≤ vσi , lo que implica que λ ≤ (v − 1)σi .
Entonces, cuanto mayor es v, más probabilidad hay de encontrar la primera colisión de la
forma xσi = xσi +λ . Tras un análisis más exhaustivo de la inuencia de ambos parámetros en
el coste computacional del algoritmo y a la vista de resultados experimentales, Teske decide
utilizar v =3 y t = 8. Para estos valores, si la función de iteración se comporta como una
√
función aleatoria el número de iteraciones está acotado por aproximadamente 1,42 n y, como
para cada iteración hay una evaluación y 8 iteraciones, si el coste de las comparaciones es
depreciable, se trata de un método mejor que el de Brent.

Ejemplo 5.11. Utilización del algoritmo de Teske para hallar una colisión en la secuencia del
ejemplo 5.7:

5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 32

i xi ∃j : xi = xσj i ≥ 3σ1 (xσ1 , ..., xσ8 ) σ1 3σ1

1 5 − − (5,5,5,5,5,5,5,5) 1 3
2 7 no no (5,5,5,5,5,5,5,5) 1 3
3 8 no sí (5,5,5,5,5,5,5,8) 1 3
4 22 no sí (5,5,5,5,5,5,8,22) 1 3
5 33 no sí (5,5,5,5,5,8,22,33) 1 3
6 15 no sí (5,5,5,5,8,22,33,15) 1 3
7 46 no sí (5,5,5,8,22,33,15,46) 1 3
8 39 no sí (5,5,8,22,33,15,46,39) 1 3
9 11 no sí (5,8,22,33,15,46,39,11) 1 3
10 12 no sí (8,22,33,15,46,39,11,12) 3 9
11 31 no sí (22,33,15,46,39,11,12,31) 4 12
12 26 no sí (33,15,46,39,11,12,31,26) 5 15
13 8 no no (33,15,46,39,11,12,31,26) 5 15
14 22 no no (33,15,46,39,11,12,31,26) 5 15
15 33 sí − − − −
El algoritmo ha encontrado la colisión x5 = x15 .

Las siguientes son variantes del método ρ basadas en funciones de iteración diferentes
debidas a Teske [29].

Función de Pollard generalizada: consiste en modicar ligeramente la denición de la

función utilizada por Pollard. Tomamos M = gm y K = ak , donde m y k son enteros
elegidos al azar tales que 1 ≤ m, k ≤ n, y una partición de G que verique los mismos
requisitos que en el método original. Denimos, entonces:


 xi K si xi ∈ S1
xi+1 = fP G (xi ) = x2 si xi ∈ S2
 i
xi M si xi ∈ S3

La varianza de µ+λ en este caso es menor que en el algoritmo de Pollard original. Esto
quiere decir que los valores de µ+λ obtenidos en distintos ejemplos se alejan menos de
E(µ + λ) que con la función original. Es por eso que esta versión puede ser considerada
como una versión controlada del método de Pollard.

Teske's Adding-walk: se trata de una mejora basada en la utilización de r particiones

en lugar de 3 que reduce el número de iteraciones. Se toman 2r enteros aleatorios mi , ki
con1 ≤ mi , ki ≤ n para i = 1, ..., r y a partir de ellos se calculan los r multiplicadores
Mi = g mi aki para i = 1, ..., r. Se dene también una función hash:

v : G −→ {1, 2, ..., r}

Entonces, la función de iteración se dene de la siguiente manera:

xi+1 = fT A (xi ) = xi Mv(xi )

En este caso, es fácil ver que los exponentes se actualizan como sigue:

αi+1 = αi + mv(xi )
βi+1 = βi + kv(xi )
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 33

En grupos de orden primo, tomando una partición con más de 16 subconjuntos y uti-
√
lizando el algoritmo de detección de ciclos de Teske, se tiene que E(µ + λ) ≈ 1,45 n
(Teske [29]). Se mejora, por tanto, la media del número de iteraciones obtenida para los
subgrupos de orden primo de F∗p con la función de iteración original.

Teske's Mixed-walk: su estructura es una mezcla entre el Teske's Adding-walk y pasos

consistentes en elevar al cuadrado. La función iteración se dene de la siguiente manera:


xi Mv(xi ) si v(xi ) ∈ {1, 2, ..., r}
xi+1 = fT M (xi ) =
x2i en otro caso

En [29], resultados experimentales muestran que tomando r ≥ 16 y q/r ≈ 0,25, donde

q es el número de pasos consistentes en elevar al cuadrado, fT M se comporta como una
√
verdadera función aleatoria. Si tomamos r = 16 y q = 4, se tiene que E(µ + λ) ≈ 1,3 n,
√
un valor cercano a la cota óptima 1,25 n aportada en el Teorema 5.5.

5.1.4. Algoritmo del canguro de Pollard

El algoritmo del canguro de Pollard [23], también conocido como algoritmo λ de Pollard,
busca el logaritmo discreto, k, en un intervalo [c, d] ⊆ Zn . En caso de no conocer el intervalo
al que pertenece el logaritmo discreto, se pueden establecer c = 0 y d = n − 1, pero en tal caso
es más eciente el algortimo ρ.

En primer lugar, se elige un conjunto de enteros S y se dene una función pseudoaleatoria

f : G −→ S . A continuación, se escoge un entero N y se calcula la secuencia {xi }N
i=0 (el camino
trazado por un canguro domesticado en N saltos) de la siguiente manera:

x0 = g d ; xi+1 = xi g f (xi )

N
X −1
Seguidamente se calcula: t= f (xi ). Obsérvese que xN = x0 g t = g d+t . En este punto,
i=0
el canguro domesticado tiende una trampa.

Se determina después la sucesión {yi }i∈N (el camino trazado por un canguro salvaje ) como
sigue:
y0 = a; yi+1 = yi g f (yi )
j−1
X
y una secuencia de enteros {tj }j∈N : tj = f (yi ). Nótese que yi = y0 g ti = ag ti .
i=0
Se dejan de calcular términos de las secuencias cuando se da una de las siguientes opciones:

1. yj = xN para algún j, esto es, el canguro salvaje cae en la trampa tendida por el
canguro domesticado. En este caso se tiene que g d+t = xN = yj = ag tj y, por tanto,
g d+t−tj =a= g k . En consecuencia, k ≡ d + t − tj (mód n).

2. tj > d − c + t. Si esto sucede, no es posible hallar k puesto que d + t − tj < c, lo que

contradice la hipótesis de que k ∈ [c, d]. En este caso, hay que aplicar el método de
nuevo, con S y/o f diferentes.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 34

Este método es conocido como método del canguro de Pollard. Dicho nombre surge de la
analogía establecida entre el hallazgo de un punto común de las sucesiones y la trampa tendida
por un canguro domesticado a un canguro salvaje. También recibe el nombre de método λ de
Pollard como alusión a la similitud entre la visualización del algoritmo y dicha letra griega. El
trazo corto corresponde a la secuencia {xi }N
i=0 y el largo a {yi }i∈N que coincide con la primera
secuencia en xN y después continúa.

Ejemplo 5.12. Considérese el grupoF∗23 . Aplicando el algoritmo del canguro de Pollard, es

posible calcular el logaritmo discreto de 17 en base 7, sabiendo que pertenece al intervalo [0, 7].

1. Se toma f (x) = x2 como función pseudoaleatoria.

2. Tomando N = 4, se genera la secuencia {xi }4i=0 :

x0 ≡ 77 ≡ 5 (mód 23)
2
x1 ≡ 5 · 75 ≡ 13 (mód 23)
2
x2 ≡ 13 · 713 ≡ 21 (mód 23)
2
x3 ≡ 21 · 721 ≡ 9 (mód 23)
2
x4 ≡ 9 · 79 ≡ 11 (mód 23)

Entonces, d + t = 7 + 52 + 132 + 212 + 92 ≡ 19 (mód ϕ(23))

3. Se generan términos de la secuencia {yi }i∈N hasta hallar una colisión:

y0 ≡ 17 (mód 23)
2
y1 ≡ 17 · 717 ≡ 12 (mód 23)
2
y2 ≡ 12 · 712 ≡ 8 (mód 23)
2
y3 ≡ 8 · 78 ≡ 18 (mód 23)
2
y4 ≡ 18 · 718 ≡ 16 (mód 23)
2
y5 ≡ 16 · 716 ≡ 9 (mód 23)
2
y6 ≡ 9 · 79 ≡ 11 (mód 23)

Por tanto, k + t6 = k + 172 + 122 + 82 + 182 + 162 + 92 ≡ 14 (mód ϕ(23)).

Como x4 = y6 , se tiene que k + t6 ≡ d + t (mód ϕ(23)) y, en consecuencia, k = 19 − 14 = 5.

Es decir, 75 ≡ 17 (mód 23).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 35

5.2. Algoritmo de Silver-Pohlig-Hellman

El algoritmo de Silver-Pohlig-Hellman [22] es un método utilizado para resolver el pro-

blema del logaritmo discreto en grupos cuyo orden, n, tiene divisores primos pequeños. Por
lo tanto, no puede aplicarse en cualquier grupo, pero en aquellos en los que puede utilizarse
resulta más eciente que los métodos genéricos.

El primer paso de este algoritmo consiste en calcular, para cada primo p divisor de n, las
p-ésimas raíces de la unidad:

rp,j = g jn/p para j = 0, ..., p − 1

Nuestro objetivo es hallar k , tal que g k = a. Dada la descomposición en factores primos

α k basta calcular k (mód pα ) para cada primo y aplicar después
Q
de n, n = p p , para hallar
el teorema chino de los restos para obtener k (mód n).

Veamos cómo calcular k (mód pα ) para cada p. Supongamos que tenemos la escritura de
k en base p:
k ≡ k0 + k1 p + ... + kα−1 pα−1 (mód pα ) con 0 ≤ ki < p
Para determinar k debemos hallar k0 , k1 , ..., kα−1 .

Para hallar k0 calculamos an/p . Como an ≡ 1 (mód n), se obtiene una raíz p-ésima de la
unidad. Además,

α−2 )n
an/p ≡ g kn/p ≡ g k0 n/p g (k1 +...+kα−1 p ≡ g k0 n/p ≡ rp,k0 (mód n)

y, por lo tanto, para determinar k0 basta con comparar an/p con las raíces p-ésimas de la
unidad previamente calculadas y establecer k0 = j para j tal que an/p = rp,j .

A continuación, para obtener k1 , reemplazamos a por a1 = a/g k0 que tiene logaritmo

discreto k − k0 ≡ k1 p + ... + kα−1 pα−1 (mód pα ). Como a1 es una potencia de orden p, se tiene
n/p
que a1 ≡ 1 (mód n) y
n/p2 2 α−2 )n/p
a1 ≡ g (k−k0 )n/p ≡ g (k1 +...+kα−1 p ≡ g k1 n/p ≡ rp,k1 (mód n)
n/p2
Luego, para hallar k1 debemos comparar a1 con las raíces p-ésimas de la unidad y tomar
n/p2
k1 = j para j tal que a1 = rp,j .

Se procede de la misma manera para hallar k2 , k3 , ..., kα−1 . En general, para obtener ki se
toma
i−1
ai = a/g k0 +k1 p+...+ki−1 p
que tiene logaritmo discreto k − (k0 + k1 p + ... + ki−1 pi−1 ) ≡ ki pi + ... + kα−1 pα−1 (mód pα ).
Como ai es una potencia
i
de orden p , se tiene que

n/pi i α−1 )n/pi

ai ≡ g (ki p +...+kα−1 p ≡1 (mód n)

y
n/pi+1 α−i )n/p
ai = g (ki +ki+1 p+...+kα−1 p = g ki n/p = rp,ki (mód n)
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 36

n/pi+1
Entonces, tomamos ki igual al valor j para el que ai = rp,j . Una vez determinados todos
los coecientes k0 , k1 , ..., kα−1 , obtenemos k (mód pα ).

Hemos de repetir estos cálculos para cada factor primo de n y una vez dispongamos de
k (mód pα ) para todo p, sólo resta aplicar el teorema chino de los restos para hallar k (mód n).

Este algoritmo funciona bien cuando todos los factores primos de n son pequeños. Obvia-
mente, si entre ellos hubiese algún primo grande (característica que depende de la capacidad de
cálculo), la determinación de la tabla con las raíces p-ésimas de la unidad y las comparaciones
n/pi+1
de yi con dicha tabla llevarían mucho tiempo.

Ejemplo 5.13. Sea q = 37. El elemento g=2 es un generador de F∗q . Además, n = q−1 =
22 32 . Se quiere calcular el logaritmo discreto en base 2 de 28 utilizando el algoritmo de Silver-
Pohlig-Hellman. El primer paso es la precomputación de las raíces p-ésimas de la unidad para
p=2 y p=3 tal y como se ha explicado.

j
HH
HH 0 1 2
p H
H
2 1 -1 -
3 1 26 10

Esto es, r2,0 = 1, r2,1 = −1, r3,0 = 1, r3,1 = 26 y r3,2 = 10.

Se pasa entonces a calcular el logaritmo discreto de a = 28 en bases 22 y 32 .

Para p = 2, k ≡ k0 + k1 2 (mód 22 ).
2836/2 ≡ 1 ≡ r2,0 (mód 37). Entonces k0 = 0.
(28/20 )36/4 ≡ −1 ≡ r2,1 (mód 37). Por tanto, k1 = 1.
2
Así, k ≡ 2 (mód 2 ).

Para p = 3, k ≡ k0 + k1 3 (mód 32 ).
2836/3 ≡ 26 ≡ r3,1 (mód 37). En consecuencia, k0 = 1.
(28/21 )36/9 ≡ 10 ≡ r2,1 (mód 37). Por consiguiente, k1 = 2.
2
Entonces, k ≡ 1 + 2 · 3 ≡ 7 (mód 3 ).

Se tiene el siguiente sistema de congruencias:


k≡2 (mód 4)
k≡7 (mód 9)

Por el teorema chino de los restos, k ≡ 34 (mód 37) y, por tanto, el logaritmo discreto de
28 en base 2 es 34.

5.3. Index-Calculus

En las secciones anteriores se han visto algunos algoritmos genéricos y el algortimo de

Silver-Pohlig-Hellman. Supongamos ahora que queremos resolver el problema del logaritmo
discreto en el grupo F∗2127 . En tal caso, el orden del grupo es 2127 − 1, un primo de Mersen-
ne grande, así que no podemos aplicar Silver-Pohlig-Hellman y los algoritmos genéricos no
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 37

resultan ecientes por el gran tamaño del grupo. En esta sección se muestra el algoritmo deno-
minado Index-Calculus, un método que sólo puede utilizarse en ciertos grupos entre los que se
encuentran los grupos multiplicativos de los cuerpos nitos. La pérdida de generalidad de este
método se compensa con una mayor eciencia que surge de sacar provecho de las propiedades
particulares del grupo.

El primero en introducir la idea básica del Index-Calculus fue Kraitchik en 1922. Merkle la
redescubrió en 1977 cuando el PLD comenzó a adquirir importancia pero fue Adleman quien
optimizó el algoritmo y lo presentó tal y como hoy lo conocemos en 1979 [1].

Para estudiar este método, se introducen primero los pasos generales del algoritmo y, a
continuación, se estudiará su aplicación en los grupos multiplicativos de los cuerpos Fpm . Cabe
mencionar que, en esta sección, indg (x) denota el logaritmo discreto en base g de x.

La idea de este algoritmo consiste en explotar la representación de los elementos del grupo
como producto de elementos de un subconjunto pequeño, la base de factores. Dado G de orden
n, tomamos B = {p1 , p2 , ..., pr } ⊆ G. El algoritmo consta, básicamente, de tres etapas:

1. Buscar identidades del tipo:

r
Y
pαi i = g t , t ∈ Z
i=1

de donde se deduce que:

r
X
αi indg (pi ) ≡ t (mód n) (5.2)
i=1

2. Una vez halladas sucientes identidades del tipo (5.2), esto es, r linealmente indepen-
dientes,tenemos un sistema compatible determinado cuyas incógnitas son los índices de
los elementos de la base de factores. Resolviendo dicho sistema, se determina el logaritmo
discreto de los elementos pi .
Estas dos etapas constituyen una precomputación que no depende del elemento del que
queremos calcular el logaritmo discreto. Sólo debemos llevarlas a cabo una vez y podemos
utilizar el resultado para calcular varios logaritmos discretos en base g.

3. Para obtener el logaritmo discreto de a se busca una relación de la forma:

r
pβi i = ag e , e ∈ Z
Y

i=1

que equivale a:
r
Y
g indg (pi )βi = g indg (a) g e , e ∈ Z
i=1

De donde se deduce:

r
X
indg (a) ≡ βi indg (pi ) − e (mód n)
i=1

Resolviendo esta última equivalencia se obtiene k = indg (a).

CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 38

Como ya hemos comentado, el Index-Calculus puede aplicarse al grupo multiplicativo de

un cuerpo nito. En lo que sigue vamos a centrarnos en aplicar este algoritmo a F∗q donde
q= pm es una potencia de primo.

En el caso en que m = 1, esto es, cuando trabajamos en Fp las factorizaciones de las

etapas 1 y 3 se pueden entender como factorizaciones de enteros menores que p. Como se
dispone de métodos ecaces para factorizar enteros como producto de primos conocidos, se
toma como base de factores un conjunto de números primos. En tal caso, el método no entraña
mayor dicultad que calcular potencias de g y escribirlas como producto de los factores que
conforman la base. Veamos un ejemplo ilustrativo.

Ejemplo 5.14. Supóngase que se quiere resolver 2k ≡ 13 (mód 2027). Lo primero que se
debe hacer es escoger una base de factores, por ejemplo B = {2, 3, 5, 7, 11}. A continuación se
calculan potencias aleatorias de g ≡ 2 (mód 2027) y se toman aquellas que pueden escribirse
como producto de elementos de B :

2293 ≡ 63 ≡ 32 · 7 (mód 2027)

983
2 ≡ 385 ≡ 5 · 7 · 11 (mód 2027)
21318 ≡ 1408 ≡ 27 · 11 (mód 2027)
1593
2 ≡ 33 ≡ 3 · 11 (mód 2027)
1918 6 2
2 ≡ 1600 ≡ 2 · 5 (mód 2027)

Se tienen, por tanto, las siguientes equivalencias:

293 ≡ 2ind2 3 + ind2 7 (mód 2026)

983 ≡ ind2 5 + ind2 7 + ind2 11 (mód 2026)
1318 ≡ 7ind2 2 + ind2 11 (mód 2026)
1593 ≡ ind2 3 + ind2 11 (mód 2026)
1918 ≡ 6ind2 2 + 2ind2 5 (mód 2026)

Como son 5 equivalencias linealmente independientes no es necesario buscar más y se puede

pasar a resolver el sistema para obtener los índices de los elementos de la base. Dado que
2026 = 2 · 1013, se resuelve el sistema módulo 2 y módulo 1013 y se aplica el teorema chino
de los restos. Se tiene entonces el siguiente sistema módulo 2:

ind2 7 ≡ 1 (mód 2)
ind2 5 + ind2 7 + ind2 11 ≡ 1 (mód 2)
ind2 2 + ind2 11 ≡ 0 (mód 2)
ind2 3 + ind2 11 ≡ 1 (mód 2)
(5.3)

Nótese que ind2 2 = 1 siempre. Entonces, ind2 2 ≡ ind2 5 ≡ ind2 7 ≡ ind2 11 ≡ 1 (mód 2) y
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 39

ind2 3 ≡ 0 (mód 2). Por otra parte se tiene el siguiente sistema módulo 1013:

2ind2 3 + ind2 7 ≡ 293 (mód 1013)

ind2 5 + ind2 7 + ind2 11 ≡ 983 (mód 1013)
ind2 11 ≡ 298 (mód 1013)
ind2 3 + ind2 11 ≡ 580 (mód 1013)
2ind2 5 ≡ 899 (mód 1013)

Entonces:

ind2 2 ≡ 1 (mód 1013) y ind2 2 ≡ 1 (mód 2)

ind2 3 ≡ 282 (mód 1013) y ind2 3 ≡ 0 (mód 2)
ind2 5 ≡ 956 (mód 1013) y ind2 5 ≡ 1 (mód 2)
ind2 7 ≡ 742 (mód 1013) y ind2 7 ≡ 1 (mód 2)
ind2 11 ≡ 298 (mód 1013) y ind2 11 ≡ 1 (mód 2)

Y, empleando el teorema chino de los restos para cada índice, nalmente se obtiene que:

ind2 2 ≡ 1 (mód 2026)

ind2 3 ≡ 282 (mód 2026)
ind2 5 ≡ 1969 (mód 2026)
ind2 7 ≡ 1755 (mód 2026)
ind2 11 ≡ 1311 (mód 2026)

Como ya son conocidos los índices de los elementos de la base, se puede pasar a la última
etapa del algoritmo. Tomando e = 1397,

13 · 21397 ≡ 110 ≡ 2 · 5 · 11 (mód 2026)

Se tiene entonces que:

ind2 13 + 1397ind2 2 ≡ ind2 2 + ind2 5 + ind2 11 (mód 2026)

Y nalmente:
ind2 13 ≡ −1397 + 1 + 1969 + 1311 ≡ 1884 (mód 2026)
Supóngase ahora que m 6= 1, esto es, q = pm es una potencia de un primo pequeño para
el que es posible resolver el logaritmo discreto de manera ecaz. Supóngase también que g es
∗
un generador de Fq . Sea f (x) ∈ Fp [x] un polinomio irreducible de grado m. Entonces Fq es
isomorfo a Fp [x]/f (x) y todo elemento a ∈ Fq puede escribirse como un polinomio a(x) ∈ Fp [x]
de grado menor que m, en particular, g = g(x) y a = a(x). Las constantes son los elementos
0
de Fp ⊂ Fq . Además, g = g
(q−1)/(p−1) genera F∗ . Para verlo ha de probarse que g 0 ∈ F∗ y que
p p
su orden es p − 1:

Para ver que g0 es un elemento de Fp basta ver que σ(g 0 ) = g 0 donde σ es el automorsmo
de Frobenius de Fq que eleva cada elemento a la potencia p. Se debe probar entonces
que (g 0 )p = g 0 .
m m−1 m−2 m−3
(g 0 )p = g p(q−1)/(p−1) = g p(p −1)/(p−1) = g p(p−1)(p +p +p +...+1)/(p−1) =
m−1 m−2 m−1 m−2 m−1 m−2 +...+p+1 = g (q−1)/(p−1) = g 0
gq gp +p +...+p = g · g p +p +...+p = g p +p
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 40

Obviamente g 0 6= 0 ya que g 6= 0 y, por lo tanto, g 0 ∈ F∗p .

Véase que el orden de g0 es p − 1. Obviamente,

(g 0 )p−1 = g (p−1)(q−1)/(p−1) = g q−1 = 1

puesto que g tiene orden q − 1. Por lo tanto, el orden de g 0 es divisor de p − 1.

Supóngase que el orden
0
de g , d, es un divisor propio de p − 1. Entonces:

(p−1)
1 = (g 0 )d = g (q−1)d/(p−1) = g (q−1)/ d

(p−1)
Pero g tiene orden exactamente q − 1 y, por lo tanto, g (q−1)/ d no puede ser 1. Así,
0
queda probado que g tiene orden p − 1.

En consecuencia, para calcular el logaritmo discreto de las constantes de F∗p [x], esto es, los
∗
elementos de Fp , en base g , basta con calcular el logaritmo discreto de las mismas en base g
0
∗
en Fp . Nótese que esta tarea es sencilla puesto que p es pequeño y puede construirse fácilmente
la tabla de logaritmos discretos o emplearse alguno de los métodos estudiados con anterioridad.

Una vez hechas estas consideraciones, se van a analizar las etapas del algoritmo. En primer
lugar, se toma B como el conjunto de todos los polinomios mónicos irreducibles sobre Fp de
grado menor o igual que k, donde k ≤ m. Se tiene que p = Fp ≤ #B ≤ Fq = m
p . Ha de
comentarse que el tamaño de B crece rápidamente a medida que m crece y teniendo en cuenta
que debemos encontrar al menos #B congruencias para resolver un sistema con el mismo
número de incógnitas, sería conveniente que el cardinal de B no fuese muy grande. Por otro
lado, si #B es muy pequeño, resultaría muy costoso encontrar simplemente una congruencia
de las necesarias. Por lo tanto, m debe tener un tamaño moderado.

Se pasa entonces a la primera etapa del algoritmo. Para ello, se toma un entero t tal que
1≤t≤q−2 y se calcula:
c(x) ≡ g(x)t (mód f (x))
Se quiere ver que c(x) puede escribirse:
Y
c(x) ≡ c0 p(x)αp (mód f (x))
p(x)∈B

Si, efectivamente, se ha encontrado una igualdad de ese tipo, tomando logaritmos discretos a
ambos lados de la misma se obtiene que:
X
ind(c(x)) − ind(c0 ) ≡ αp ind(p(x)) (mód q − 1)
p(x)∈B

Nótese que ind(c(x)) = t y que ya se había calculado ind(c0 ) ya que c0 es una constante en F∗p [x]

Como ya se ha comentado, una vez obtenidas #B equivalencias de este tipo, se está en

disposición de ejecutar el paso 2 del algoritmo para determinar el índice de todos los elementos
de #B . Tras ello, se pasa a la tercera y última etapa del Index-Calculus. En dicha etapa, ha
de encontrarse, de la misma manera que el paso 1, una relación de la forma
Y
a(x)g(x)t ≡ a0 p(x)αp (mód f (x))
p(x)∈B
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 41

Como ya se explicó, se tiene así que

X
ind(a(x)) + t ≡ ind(a0 ) + αp ind(p(x)) (mód q − 1)
p(x)∈B

y, por el isomorsmo,
X
ind(a) ≡ ind(a0 ) + αp ind(p(x)) − t (mód q − 1)
p(x)∈B

Claramente, la complejidad del algoritmo reside en la factorización que se lleva a cabo en

los pasos 1 y 3. De ahí la importancia de disponer de métodos ecaces de factorización de
polinomios. En el apartado siguiente, se estudian algunos de esos métodos.

5.3.1. Factorización de polinomios en cuerpos nitos

Para empezar, conviene hacer algunas consideraciones:

Sean g(x) polinomios tales que g(x) divide a f (x). Se llamará exponente de g(x)
f (x) y
e
al mayor entero e tal que g (x) divide a f (x). Si e es mayor que 1, se dice que g(x) es
un factor repetido de f (x).

Todo polinomio mónico de un cuerpo nito puede ser factorizado de forma única como
producto de polinomios irreducibles. Se trata de la factorización canónica de un poli-
nomio y es la factorización que se quiere calcular. Es decir, si f (x) es un polinomio de
Fq [x] de grado n, se van a buscar polinomios irreducibles pi y enteros ei tales que:

m
Y
f (x) = pei i (x)
i=0
Qm ei
Si en la expresión anterior los polinomios pi no son irreducibles, se dice que i=0 pi (x)
es una factorización parcial de f (x) (suponiendo no sea trivial).

En lo que sigue, salvo que se especique otra cosa, se considera que f (x) es un polinomio
mónico de Fq [x] de grado n.

Se introducirán dos tipos de factorizaciones parciales y algoritmos para calcularlas. Asi-

mismo, se presentarán dos algoritmos para factorizar polinomios que disponen de ciertas pro-
piedades. Combinando ambas cosas será posible factorizar cualquier polinomio sobre cualquier
cuerpo nito.

Factorización libre de cuadrados

En primer lugar, es necesario introducir la siguiente denición:

Denición 5.15. Se dice que un polinomio f (x) es libre de cuadrados si no existe ningún
polinomio g(x) tal que g 2 (x) divida a f (x). Si f (x) es un polinomio no libre de cuadrados,
entonces existe g(x) tal que g 2 (x) divide a f (x) y h(x) = f (x)/g 2 (x) es libre de cuadrados. El
polinomio h(x) se denomina parte libre de cuadrados de f (x).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 42

n
X n
X
i
Dado f (x) = ai x 0
, se dene la derivada de f (x), f (x), como f 0 (x) = iai xi−1 .
i=0 i=1
Es fácil comprobar que la derivada de un polinomio satisface:

(f (x)e )0 = ef (x)e−1 f 0 (x)

(f g)0 (x) = f 0 (x)g(x) + f (x)g 0 (x)

Si un polinomio f (x) no es libre de cuadrados, entonces f (x) y su derivada, f 0 (x), tienen
factores comunes, tal y como se pone de maniesto en el siguiente lema:

Lema 5.16. Sea f (x) un polinomio no libre de cuadrados. Sea g(x) un factor repetido de f (x)
con exponente e. Entonces g(x) es un factor de f 0 (x) con exponente e0 = e − 1.
Demostración. Sea h(x) = f (x)/g(x)e . Entonces f (x) = h(x)g(x)e . Utilizando las propiedades
de la derivada:

f 0 (x) = h0 (x)g(x)e + h(x)eg(x)e−1 = g(x)e−1 (h0 (x)g(x) + eh(x)g(x))

Nótese que e−1>0 ya que e>1 por ser g(x) factor repetido.

Corolario 5.17. Para todo polinomio f (x), el polinomio f (x)/mcd(f (x), f 0 (x)) es libre de
cuadrados.
Demostración. Sean q0 (x), q1 (x), ..., qk (x) polinomios irreducibles tales que existen e0 , e1 , ..., ek
todos mayores que 1 de manera que:

f (x)
h1 (x) = Qk ei
i=0 qi (x)

sea libre de cuadrados. Entonces, por el lema 5.16, cada qi (x) es factor de f 0 (x) con exponente
e i − 1, es decir:
f 0 (x)
h2 (x) = Qk ei −1
i=0 qi (x)
es libre de cuadrados. Entonces,

k
qiei −1 (x) mcd(h1 (x), h1 (x))
Y
mcd(f (x), f 0 (x)) =

i=0

y, por tanto,
Qk

f (x) i=0 qi (x) h1 (x)
=
mcd(f (x), f 0 (x)) mcd(h1 (x), h2 (x))
Como cada qi (x) qi (x) es libre de cuadrados. Por otro lado,
es irreducible, el producto de los
como h1 h1 (x)/mcd(h1 (x),
no tiene factores repetidos,
Qk h2 (x)) también es libre de cuadrados.
Además, por la manera en que se ha denido h1 (x), i=0 qi (x) y h1 (x)/mcd(h1 (x), h2 (x)) son
coprimos y en consecuencia su producto tampoco tiene factores repetidos.

Observación 5.18. Sea f (x) ∈ Fq [x] con q = pn . Entonces, char(Fq ) = p. Si f (x) es tal
que existe g(x) con f (x) = g(x)p , se tiene que f 0 (x) = pg(x)p−1 = 0. Por tanto, el re-
sultado del lema anterior resulta trivial ya que mcd(f (x), f 0 (x)) = f (x) y, en consecuencia,
f (x)/mcd(f (x), f 0 (x)) = 1 que, obviamente, no tiene factores repetidos. En este caso, se podría
encontrar un factor no trivial de f (x) calculando gcd(g(x), g 0 (x)).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 43

Los resultados presentados permiten calcular una factorización parcial cuyos factores son
libres de cuadrados. El siguiente algoritmo realiza este proceso:

Algoritmo 5.19. LIBRE DE CUADRADOS

Input: f (x) ∈ Fq (x)

Qk
Output: f1 (x), f2 (x), ..., fk (x) con f (x) = i=0 fi (x)

1. i := 1

2. Mientras f (x) 6= 1 hacer:

a) Si mcd(f (x), f 0 (x)) 6= f (x) hacer:
1) fi (x) := f (x)/mcd(f (x), f 0 (x))
2) f (x) := f (x)/fi (x)
3) i := i + 1
b) si no, hacer:
1) Tomar k como la mayor potencia de p que divide a todas las potencias de x en
j
f (x), esto es, k = máx{j : xp | xh , ∀ xh monomio de f (x)}
k
2) g(x) := f (x)1/p
3) fi (x) := g(x)/mcd(g(x), g 0 (x))
4) f (x) := f (x)/fi (x)
5) i := i + 1

3. Devolver: {f1 (x), ..., fi−1 (x)}

Si mcd(f (x), f 0 (x)) 6= f (x), entonces el polinomio f (x) no es potencia de orden p de
ningún otro polinomio y, por el Corolario 5.17, cada fi (x) obtenido en este caso no tiene
factores repetidos.
mcd(f (x), f 0 (x)) = f (x), a partir de la observación 5.18, se calcula un polinomio g(x)
Si
que no es potencia de orden p de ningún otro. A continuación se halla un factor libre de
cuadrados de f (x) tomando uno de los factores con esta propiedad de g(x).
Por tanto, en cada iteración i se obtiene un factor fi (x) del polinomio original. Además,
el valor de f (x) se actualiza por el cociente de f (x)/fi (x). Este proceso se realiza hasta que
el polinomio almacenado en f (x) sea irreducible o producto de irreducibles. En cualquiera de
los dos casos, se puede comprobar que el valor de f (x) tras actualizarse es exactamente 1 y,
por consiguiente, el algoritmo termina.
Qi−1
Además, cuando el proceso acaba, el valor de f (x) está actualizado por fO (x)/ i=1 fi (x),
donde fO (x) es el polinomio original. Como el criterio de parada es f (x) = 1, es obvio que el
producto de los factores obtenidos es, efectivamente, el polinomio original.

Nótese que los polinomios fi (x) obtenidos no tienen porqué ser irreducibles ni diferentes.
Sólo se asegura que son libres de cuadrados.

Ejemplo 5.20. Se va a calcular una factorización libre de cuadrados de f (x) = x4 + 2x3 −

4x2 − 2x + 3 en F5 [x].
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 44

1. i=1: f 0 (x) = 4x3 + 6x2 − 8x − 2, mcd(f (x), f 0 (x)) = x − 1 6= f (x)

f (x) f (x)
f1 (x) = 0
= = x3 + 3x2 − x − 3
mcd(f (x), f (x)) x−1
f (x)
f (x) = =x−1
f1 (x)
2. i=2: f 0 (x) = 1 y mcd(f (x), f 0 (x)) = 1 6= f (x)
f (x)
f2 (x) = =x−1
1
f (x)
f (x) = =1
f2 (x)
y el algoritmo termina.

Se obtiene la siguiente factorización libre de cuadrados:

f (x) = (x3 − 3x2 − x + 3)(x − 1)

Esta factorización no coincide con la factorización canónica de f (x):

f (x) = (x − 1)2 (x + 1)(x + 3)

Factorización distinto grado

Se introduce el siguiente lema, que será la base del algoritmo presentado para obtener la
factorización parcial deseada:

Lema 5.21 (Lema del producto de Gauss) .

Dado n ∈ N, el producto de todos los polinomios
n
mónicos e irreducibles de Fq [x] de grado d tal que d | n es el polinomio xq − x.
El algoritmo descrito a continuación factoriza un polinomio libre de cuadrados f (x) co-
mo producto de polinomios cuyos factores irreducibles son todos del mismo grado, esto es,
encuentra polinomios f1 (x), f2 (x), ..., fk (x) tales que:

k
Y
f (x) = fi (x)
i=1

donde cada fi (x) verica:

mi
Y ei
fi (x) = qj j (x)
j=1

siendo todos todos los qi (x) polinomios irreducibles de grado i.

Algoritmo 5.22. DISTINTO GRADO

Input f (x) ∈ Fq [x] libre de cuadrados de Qgrado n

Output f1 (x), ..., fk (x) tales que f (x) = ki=1 fi (x) y todos los factores irreducibles de fi (x)
tienen grado i
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 45

1. i := 1
2. Mientras deg(f (x)) > 0 hacer:
i
a ) fi (x) := mcd(f (x), xq − x)
b ) f (x) := f (x)/fi (x)
c ) i := i + 1
3. Devolver: {f1 (x), f2 (x), ..., fi−1 (x)}
i
En cada iteración i, gcd(f (x), xq − x) es el producto de todos los factores irreducibles
de f (x) de grado divisor de i por el Lema del producto de Gauss y porque f (x) es libre
de cuadrados. Como todos los factores de grado menor que i son eliminados de f (x) en los
qi
pasos anteriores, el mcd(f (x), x − x) es el producto de todos los divisores de f (x) de gra-
do precisamente i. Si el divisor irreducible de mayor grado de f (x) tiene grado k , entonces
en la iteración k , f (x)/fk (x) = 1. Por tanto, en este paso deg(f (x)) = 0 y el algoritmo termina.

Nótese que si todos los factores irreducibles de f (x) tienen distinto grado, entonces la
factorización obtenida por el algoritmo anterior es la factorización canónica de f (x).
Ejemplo 5.23. Sea f (x) = x5 +2x4 −x−2 un polinomio libre de cuadrados de F3 [x]. Aplicando
el algoritmo que se acaba de describir se obtiene una factorización en polinomios cuyos factores
son todos del mismo grado.
1. i = 1
2. Como deg(f (x)) = 3 > 0,
a) f1 (x) = mcd(f (x), x3 − x) = x3 + 2x2 − x − 2
b) f (x) = f (x)/f1 (x) = x2 + 1
c) i=2
3. deg(f (x)) = 1 > 0,entonces:
a) f2 (x) = mcd(f (x), x6 − x) = x2 + 1
b) f (x) = f (x)/f2 (x) = 1
c) i=3
4. deg(f (x)) = 0 y, en consecuencia, el algoritmo termina.
Por tanto, se obtiene la factorización f (x) = (x2 + 1)(x3 + 2x2 − x − 2). Nótese que dicha
factorización no es la canónica.

Algoritmo de Berlekamp
El algoritmo de Berlekamp es un algoritmo para factorizar polinomios libres de cuadrados.
Para obtener la factorización canónica de cualquier polinomio basta con utilizar el algoritmo
5.19 primero y después aplicar Berlekamp a cada factor libre de cuadrados obtenido.

Se presentan a continuación algunos resultados necesarios para comprender el funciona-

miento del algoritmo.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 46

Lema 5.24. Todo polinomio g(x) ∈ Fq [x] satisface:

Y
g q (x) − g(x) = (g(x) − s)
s∈Fq

Demostración. Por el lema del producto de Gauss (lema 5.21), xq −x =

Q
s∈Fq (x−s). Tomando
x = g(x), se obtiene el resultado.

Teorema 5.25. Sean f (x) y g(x) polinomios mónicos de Fq [x] tales que g(x)q ≡ g(x) (mód f (x)).
Entonces: Y
f (x) = mcd(f (x), g(x) − s)
s∈Fq

Demostración. Q q
Por hipótesis, g (x) ≡ g(x) (mód f (x)), esto es, f (x) | g q (x) − g(x) y por el
lema 5.24, f (x) | s∈Fq (g(x) − s). Por tanto,
Y Y
f (x) | mcd(f (x), (g(x) − s)) = mcd(f (x), (g(x) − s))
s∈Fq s∈Fq

Por otro lado, cada término mcd(f (x), g(x) − s) del producto divide a f (x). Además,
g(x) − si y g(x) − sj son coprimos si i 6= j y, por tanto, también lo son mcd(f (x), g(x) − si ) y
mcd(f (x), g(x) − sj ). Entonces,
Y
mcd(f (x), (g(x) − s)) | f (x)
s∈Fq

En consecuencia, ambos polinomios son iguales.

Obsérvese que si g(x) tiene grado mayor o igual que uno, este teorema proporciona una
factorización no trivial de f (x). El algoritmo de Berlekamp es básicamente un algoritmo para
hallar un polinomio g(x) que satisfaga dicha condición.

El conjunto de todos los factores irreducibles de f (x) puede ser considerado como un
subconjunto de R = Fq [x]/(f (x)). Si consideramos el anillo cociente como un álgebra sobre
Fq , el conjunto de polinomios g(x) ∈ Fq [x] que satisfacen g q (x) ≡ g(x) (mód f (x)) forman
una subálgebra de R. Dicha subálgebra se conoce como la subálgebra de Belekamp de R y
se denota por B . La estrategia del algoritmo de Berlekamp es calcular una base de B para
generar polinomios de dicha subálgebra que por el teorema 5.25 proporcionarán fácilmente
una factorización no trivial de f (x). Para calcular dicha base se necesita la siguiente:

Denición 5.26. Sea f (x) un polinomio de grado n. Se denen n polinomios

n−1
X
Qi (x) = qi,j xj para i = 0, 1, ..., n − 1
j=0

donde los coecientes qi,j se toman de manera que xiq ≡ qi,n−1 xn−1 + ... + qi,0 = Qi (x)
(mód f (x)). La matriz de Berlekamp de f (x) es la matriz cuadrada de dimensión n:
 
q0,0 q0,1 ... q0,n−1
 q1,0 q1,1 ... q1,n−1 
Q= . .. .. ..
 
 .. . . .


qn−1,0 qn−1,1 ... qn−1,n−1
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 47

Los resultados presentados a continuación establecen la relación existente entre los polino-
mios de la subálgebra de Berlekamp y algunos vectores propios del endomorsmo Q.

Lema 5.27. Sea g(x) = n−1 i=0 gi x un polinomio de Fq [x] de grado menor que n. Sea g
i e el
P
vector de coecientes (g0 , g1 , ..., gn−1 ). Se tiene que:

g q (x) ≡ geQ (mód f (x))

Demostración.
n−1
X n−1
X
g q (x) = g(xq ) = gi xiq ≡ gi Qi (x) (mód f (x))
i=0 i=0

Como
n−1
X n−1
X  n−1
X  n−1
X  n−1
X  n−1
X
j j
gi Qi (x) = gi qi,j x = gi qi,j x = g Q)j xj
(e
i=0 i=0 j=0 j=0 i=0 j=0

entonces,
g q (x) ≡ geQ (mód f (x))

Corolario 5.28. Sea g(x) = n−1 i=0 gi x un polinomio de Fq (x) de grado menor que n. Se
i
P
tiene que g(x) es un elemento de la subálgebra de Berlekamp, B, si y sólo si el vector ge =
(g0 , g1 , ...gn−1 ) es un vector propio de Q asociado al valor propio 1,es decir, pertenece al núcleo
de Q − Id, donde Id es la matriz identidad.

Demostración. Por el lema anterior, g q (x) ≡ geQ (mód f (x)). Además, g(x) pertenece a B si
q
y sólo si g (x) ≡ g(x) (mód f (x)). Por tanto, que g(x) sea un elemento de B es equivalente a
decir que
geQ = g
Esto es,
ge(Q − Id) = 0
como se quería demostrar.

Por consiguiente, es necesario que 1 sea valor propio del endomorsmo Q para poder
f (x). Si 1 no es valor propio, entonces la subálgebra de Berlekamp es trivial y, en
factorizar
consecuencia, f (x) es irreducible. Este hecho se puede generalizar por el siguiente resultado:

Lema 5.29. Sea f (x) un polinomio libre de cuadrados de Fq [x]. El número de factores irre-
ducibles de f (x) es igual a la dimensión del núcleo de Q − I .

Demostración. Sea
m
Y
f (x) = pi (x)
i=1

la factorización canónica de f (x). Sea g(x) un polinomio tal que g q (x) ≡ g(x) (mód f (x)), es
decir, f (x) | g q (x) − g(x). Por el lema 5.24,

m
Y Y
pi (x) | (g(x) − s) (5.4)
i=1 s∈Fq
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 48

Los pi (x) son irreducibles y coprimos, también son coprimos los polinomios (g(x) − sj ). Por
tanto, la condición es cierta si y sólo si cada pi (x) divide a (g(x) − sj ) para algún sj ∈ Fq . Esto
es equivalente a que g(x) ≡ sj (mód pi (x)). Por el teorema chino de los restos, existe un único
g(x) vericando que g(x) ≡ sj (mód pi (x)) para i = 0, 1, ..., m. Cómo hay q m posibilidades de
establecer dichas congruencias, se puede armar que hay q
m polinomios g(x) en B . Se deduce

el resultado del corolario 5.28.

Se está ya en condiciones de presentar el algoritmo de Berlekamp.

Algoritmo 5.30. BERLEKAMP

Input f (x) ∈ Fq [x] libre de cuadrados de grado n

Output Factorización canónica de f (x)

1. Calcular la matriz de Berlekamp de f (x), Q.

2. Calcular una base B de B, esto es, una base de ker(Q − I).

3. i := 0, m := |B|

4. F = {f (x)}

5. Mientras i < m hacer:

a) Elegir ge ∈ B (ge dene un polinomio g(x))
b ) B := B \ {e
g}
c ) F 0 := {}
d) Para todo s ∈ Fq hacer:
1) h(x) := mcd(f (x), g(x) − s)
2) Si deg(h(x)) > 0, F 0 := F 0 ∪ {h(x)}
e ) C = F \ F 0; D = F 0 \ F . Si |D| > |C|, F = (F \ C) ∪ D
f ) i := |F |

En los tres primeros pasos del algoritmo, se calcula la matriz de Berlekamp asociada a
f (x), Q, y una base, B, de ker(Q − I). Por el Corolario 5.28, los polinomios correspondientes
a los vectores de B forman también una base de B.
La variable i almacena el número de factores calculados en cada paso. Por el Lema 5.29,
como f (x) es libre de cuadrados, el número de factores irreducibles de f (x) es m = |B|. Por
este motivo, el algoritmo acaba cuando ha encontrado m factores, momento en el cual dichos
factores constituyen la factorización canónica.
En cada iteración, se calcula una factorización parcial de f (x) utilizando un cierto g(x)
de B a partir del teorema 5.25. Tanto el producto de los factores almacenados en F =
{f1 (x), f2 (x), ..., fk (x)} como el de los almacenados en F 0 = {h1 (x), h2 (x), ..., hl (x)} es f (x).
Luego el producto de los elementos de C es igual al producto de los elementos de D . En efecto,
0
si F ∩ F = {fs1 (x), fs2 (x), ..., fsr (x)} = {ht1 (x), ht2 (x), ..., htr (x)}, entonces

Y f (x) f (x) Y
fi (x) = = = hj (x)
fs1 (x)...fsr (x) ht1 (x)...ftr (x)
fi (x)∈C hj (x)∈D
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 49

Así, si|D| > |C|, se actualiza F como F = (F \ C) ∪ D. Como el producto de los elementos
de C y D es el mismo, el producto de los elementos en F sigue siendo f (x). Además, como
|D| > |C|, la factorización que se almacena en F tras la actualización tiene más factores que
la almacenada anteriormente y, en consecuencia, se acerca más a la factorización canónica.

Ejemplo 5.31. Se desea calcular la factorización canónica de f (x) = x3 − 2x2 − x + 2, que

es libre de cuadrados, en F5 [x] aplicando el algoritmo de Berlekamp.

1. F = {f (x)}
 
1 0 0
2. Matriz de Berlekamp: Q = 0 1
 0 ya que x0 ≡ 1 (mód x3 − 2x2 − x + 2), x5 ≡ x
0 0 1
(mód x − 2x − x + 2) y x = x2
3 2 10 (mód x3 − 2x2 − x + 2).

3. Base de ker(Q − I): {(1, 0, 0), (0, 1, 0), (0, 0, 1)}. Entonces, m = 3.

4. ge = (0, 1, 0) y, en consecuencia, g(x) = x.

5. mcd(f (x), x) = 1; mcd(f (x), x−1) = x−1; mcd(f (x), x−2) = x−2; mcd(f (x), x−3) =
1; mcd(f (x), x − 4) = x − 4. Por tanto, F 0 = {x − 1, x − 2, x − 4}.

6. C = {f (x)}, D = {x − 1, x − 2, x − 4}. Como |D| > |C|, F = F 0 .

7. i = |F | = 3 = m y el algoritmo termina.

Así, x3 − 2x2 − x + 2 = (x − 1)(x − 2)(x − 4).

Algoritmo de Cantor-Zassenhaus
El algoritmo de Cantor-Zassenhaus es una algoritmo para factorizar polinomios cuyos fac-
tores irreducibles son todos del mismo grado. Sin embargo, se puede utilizar para hallar la
factorización canónica de un polinomio f (x) cualquiera. Para ello, basta aplicar el algoritmo
libre de cuadrados (algoritmo 5.19) a f (x) y después el algoritmo distinto grado (algoritmo
5.22) a cada uno de los factores obtenidos. Después, sólo resta utilizar Cantor-Zassenhaus en
cada uno de los factores hallados con el último algoritmo.

Los detalles del algoritmo de Cantor-Zassenhaus dependen del cuerpo Fq sobre el que se
trabaje. Es preciso diferenciar los casos en que q es una potencia de primo impar de aquellos en
los que es una potencia de 2. En lo que sigue, se considerará el primero de los casos y, tras pre-
sentar el algoritmo, se introducirán las modicaciones necesarias para que sea válido si q es par.
Qm
En lo que sigue, si f (x) = i=1 pi (x) donde los pi (x) son primos entre sí, se denota por ϕ
el isomorsmo:
Fq [x] Fq [x] Fq [x]
ϕ: −→ ⊕ ... ⊕
(f (x)) (p1 (x)) (pm (x))
g(x) 7−→ (g1 (x), ..., gm (x))
denido en el teorema 3.8 (teorema chino de los restos para polinomios).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 50

Teorema 5.32.
Qm
Sea f (x) = i=1 p1 (x)p2 (x)...pm (x) un polinomio cuyos factores sean primos
Fq [x]
entre sí dos a dos. Sea g(x) un polinomio de tal que:
(f (x))
g(x) 6= 0, ±1 y ϕ(g(x)) = (g1 , g2 , ..., gm ) con gi ∈ {0, 1, −1} para i = 1, ...m

Sean A0 = {i | gi = 0}, A1 = {i | gi = 1} y A−1 = {i | gi = −1}. Entonces, dos de estos

conjuntos son no vacíos y los polinomios asociados a dichos conjuntos de la siguiente manera:
Y
mcd(f (x), g(x)) = pi (x)
i∈A0
Y
mcd(f (x), g(x) − 1) = pi (x)
i∈A1
Y
mcd(f (x), g(x) + 1) = pi (x)
i∈A−1

son factores no triviales de f (x).

Demostración. Necesariamente dos de los conjuntos denidos son no vacíos. Si gi = 0 para
todo i, esto es, sólo A0 fuese no vacío, por el teorema chino de los restos, g(x) = 0. De igual
manera, si A1 fuese el único conjunto no vacío, g(x) = 1 y si lo fuese A−1 , se tendría que
g(x) = −1.
Se supone, sin pérdida de generalidad, que A0 y A1 i ∈ A0 ,
son no vacíos. Para todo
g(x) ≡ 0 (mód pi (x)) y, por tanto, pi (x) | g(x). Además, si i ∈ / A0 , g(x) 6≡ 0 (mód pi (x)) y,
entonces, pi (x) 6 |g(x). La denición de máximo común divisor justica que mcd(f (x), g(x)) =
Q
i∈A0 pi (x). Por
Q otra parte, como A1 es no vacío, no todos los factores de f (x) pertenecen a
A0 . Entonces, i∈A0 pi (x) 6= f (x). Q
De igual modo, se demuestra que i∈A1 pi (x) es un factor no trivial de f (x), teniendo en
cuenta que g(x) ≡ 1 (mód pi ) y, por tanto, g(x) − 1 ≡ 0 (mód pi ) para todo i en A1 .

Fq
Todo polinomio g(x) ∈ satisfaciendo las condiciones del teorema anterior propor-
(f (x))
ciona una factorización no trivial de f (x) que no ha de ser necesariamente la factorización
canónica. Sin embargo, este resultado puede aplicarse de manera recursiva a cada factor ob-
tenido hasta alcanzar la factorización deseada.

Sólo falta determinar cómo obtener un polinomio g(x) que verique las condiciones del
teorema anterior (teorema 5.32). Los resultados presentados hasta ahora son válidos para
cualquier polinomio con factores primos entre sí dos a dos. A partir de este momento, se
Qm
considera que f (x) = i=1 p1 (x)p2 (x)...pm (x) es un polinomio cuyos factores
pi (x) son primos
Fq [x]
entre sí dos a dos y, además, tienen igual grado d. Sea h(x) un polinomio cualquiera de
(f (x))
d
y sea k = (q − 1)/2.
ϕ(h(x)k ) = (bk1 (x), bk2 (x), ..., bkm (x))
Como cada pi (x) es un polinomio irreducible de grado d, cada uno de los sumandos de
Lm k (q d −1)/2
i=1 Fq [x]/ < pi (x) > es isomorfo a Fq d [x]. Entonces, hi (x) = hi (x) = ±1 si hi 6= 0
k k
para todo i = 1, ..., m. Si hi (x) = 0, hi (x) = 0. Si, además, h (x) 6= 0, ±1, dicho polinomio
satisface las condiciones del teorema 5.32.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 51

Se han presentado ya todos los resultados necesarios para justicar el funcionamiento del
algortimo.

Algoritmo 5.33. CANTOR-ZASSENHAUS

Input f (x) ∈ FqQ

[x] con todos sus factores irreducibles del mismo grado, d
Output f (x) = 3i=1 fi (x)

1. Tomar h(x) ∈ Fq [x]/ < f (x) > tal que h(x) 6= 0, ±1

d −1)/2
2. Calcular g(x) = h(x)(q

3. f1 (x) := mcd(f (x), g(x))

4. f2 (x) := mcd(f (x), g(x) − 1)

5. f3 (x) := mcd(f (x), g(x) + 1)

6. Devolver f1 (x), f2 (x), f3 (x)

Es claro que el algoritmo consiste únicamente en aplicar el teorema 5.32. Como se ha co-
mentado con anterioridad, la factorización obtenida no tiene porqué ser la canónica pero esto
se resuelve aplicando el algoritmo de manera recursiva a cada factor obtenido. La recursivi-
dad es posible porque cada factor es producto de polinomios irreducibles con el mismo grado.
Además, como el grado de los factores obtenidos va disminuyendo, el proceso termina.

Se considera ahora el caso en que q es potencia de 2. En este caso, k = (q − 1)/2 no es

un entero por lo que el proceso descrito con anterioridad no es válido. No se podrá aplicar el
teorema 5.32 sino una versión adaptada. Para factorizar en Fq [x] cuando q es par se distinguen
los casos en que q ≡ 1 (mód 3) y q ≡ 2 (mód 3).

Si q ≡ 1 (mód 3), entonces (q d − 1)/3

es un entero. En tal caso, dado h(x) ∈ Fq [x],
(q d −1)/3
k
para todo hi (x) 6= 0 se tiene que hi (x) = hi (x) ∈ {1, ρ, ρ2 }, donde ρ y ρ2 son raíces
k
cúbicas de la unidad en Fq . Sea g(x) = h (x). Se denen los conjuntos A0 = {i | gi = 0},
A1 = {i | gi = 1},Aρ = {i | gi = ρ} y Aρ2 = {i | gi = ρ2 }. Suponiendo que al menos dos de
ellos son no vacíos y razonando de la misma manera que en el teorema 5.32, se tiene que al
menos dos de los siguientes polinomios son factores no triviales de f (x):
Y
mcd(f (x), g(x)) = pi (x)
i∈A
Y
mcd(f (x), g(x) − 1) = pi (x)
i∈B
Y
mcd(f (x), g(x) − ρ) = pi (x)
i∈D
Y
mcd(f (x), g(x) − ρ2 ) = pi (x)
i∈E
Con estas modicaciones, el algoritmo de Cantor-Zassenhaus funciona.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 52

Si, por el contrario, q ≡ 2 (mód 3), no es seguro que q d ≡ 1 (mód 3) y las raíces cúbicas
utilizadas en el caso anterior no han de existir necesariamente. Sin embargo, se puede trabajar
en la extensión Fq (ρ)[x] y proceder de la misma manera que en el caso anterior para factorizar
f (x). A continuación, basta con combinar los factores que son conjugados para obtener la
factorización en Fq [x].

Ejemplo 5.34. Dado f (x) = x3 − x2 + x − 1 en F5 [x], es posible hallar su factorización

canónica utilizando el algoritmo de Cantor-Zassenhaus:

1. h(x) = x − 1
5−1
2. g(x) = (x − 1) 2 = (x − 1)2 = x2 − 2x + 1

3. f1 (x) = mcd(f (x), x2 − 2x + 1) = x − 1

4. f2 (x) = mcd(f (x), x2 − 2x) = x − 2

5. f3 (x) = mcd(f (x), x2 − 2x + 2) = x − 3

Por tanto, f (x) = (x − 1)(x − 2)(x − 3).

Los algoritmos de Berlekamp y Cantor-Zassenhaus que aquí se han presentado no son

los únicos algoritmos de factorización existentes ni los más rápidos. En cambio, son los más
utilizados por su sencillez y ecacia.
Bibliografía
[1] L. Adleman, A subexponential algorithm for the discrete logarithm problem with appli-
cations to Cryptography, Proceedings of the 20th Annual Symposium on Foundations of
Computer Science, 55-60 (1979)

[2] S. Bai and R. P. Brent, On the eciency of Pollard's rho method for discrete logarithms,
The Australasian Theory Symposium (CATS2008), Conferences in Research and Practice
in Information Technology 77, 125-131 (2008)

[3] M. Blum y S. Micali, How to generate cryptographically strong sequences of pseudorandom

bits, SIAM Journal on Computing 13(4), 850-864 (1984)

[4] B. den Boer,DieHellman is as strong as discrete log for certain primes,Advances in

Cryptology - CRYPTO '88, LNCS 403,Springer, 530-539 (1988)

[5] R.P. Brent, An Improved Monte Carlo Factorization Algorithm BIT 20(2), 176184 (1980)

[6] P. Caballero Gil, Introducción a la Criptografía, Ra-Ma (2002)

[7] A.A. Ciss, A.Y. Cheikh y D. Sow, A Factoring and Discrete Logarithm based Cryptosys-
tem, International Journal of Contemporary Mathematical Sciences 8(11), 511 - 517 (2013)

[8] [Link]e y M.E. Hellman, New directions in Cryptography, IEEE Transactions on Infor-
mation Theory 22, 644-654 (1976)

[9] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete loga-
rithms, IEEE Transactions on Information Theory 31, 469-472 (1985)

[10] B. Harris, Probability Distribution Related to Random Mappings, Annals of Mathematical

Statistics 31, 10451062 (1960)

[11] A. Kerckhos, La Cryptographie militaire, Journal des sciences militaires IX,5-23,161-193

(1883)

[12] N. Koblitz, A course in Number Theory and Cryptography, Springer-Verlag (1994)

[13] J. Massey y J.K. Omura, U.S. Patent 4,567,600 (1982)

[14] U.M. Maurer,Towards the equivalence of breaking the Die-Hellman protocol and com-
puting discrete logarithms, Advances in Cryptology - CRYPTO '94, LCNS 839, 271-281
(1994)

Public key Cryptography using discrete logarithms in nite elds: Algorithms,

[15] L. Maurits,
ecient implementation and attacks, Honours Thesis, Universidad de Adelaida (2006)

53
BIBLIOGRAFÍA 54

[16] C. Munuera y J. Tena, Codicación de la informacion, Valladolid: Secretariado de Publi-

caciones e Intercambio Cientíco, Universidad de Valladolid, (1997)

[17] NIST, DSS (Announcing the Standard for Digital Signature Standard), FIPS Publication
186 (1994)

[18] A.M. Odlyzko, Discrete logarithms in nite elds and their cryptographic signicance,
Advances in Cryptology: EUROCRYPT 84,LNCS 209,Springer, 224-314 (1984)

[19] A.M. Odlyzko, Discrete logarithms: the past and the future, Designs, Codes, and Crypto-
graphy 19, 129-145 (2000)

[20] R.W.K. Odoni, [Link] y P.W. Sanders, Public key distribution in matrix rings,
Electronic Letters 20, 386-387 (1984)

[21] R.W.K. Odoni, y [Link], Security of public key distribution in matrix rings,
Electronic Letters 22, 46-47 (1985)

[22] S. Pohlig y M. Hellman, An Improved Algorithm for Computing Logarithms over GF(p)
and its Cryptographic Signicance, IEEE Transactions on Information Theory 24, 106110
(1978)

[23] J. M. Pollard, Monte Carlo methods for index computation (mod p), Mathematics of
Computation 32(143), 918924 (1978)

[24] K. Sakurai y H. Shizuya,Relationships among the computational powers of breaking dis-

crete log cryptosystems, Eurocrypt'95, LNCS 921, 341-355(1995)

[25] D. Shanks, Class number, a theory of factorization and generation, Proceedings of Sym-
posia in Pure Mathematics 20, 415440 (1971)

[26] C.E. Shannon, A mathematical theory of Communication, The Bell System Technical
Journal, 27,379-423, 623-656 (1948)

[27] D.R. Stinson, Cryptography: theory and practice, Discrete Mathematics and its Applica-
tions,Chapman and Hall (2005)

[28] E. Teske, On random walks for Pollard's rho method, Mathematics of Computation
70(234), 809825 (2001)

[29] E. Teske, Speeding up Pollard's rho method for computing discrete logarithms, Algorithmic
Number Theory Symposium (ANTS IV), LNCS 1423, 541-553 (1998)

[30] Y. Tsiounis y M. Yung, On the security of ElGamal based encryption, Public Key Cry-
ptography, LNCS 1431, 117-134 (1998)