Siguiente: Método de llave pública Un nivel arriba: En campos finitos Anterior: Algoritmo de Silver (1978)

Algoritmo de Adleman [1979]

Sea $\alpha\in \mbox{\it GF}(p)$ un generador. Sea F un conjunto de primos en $\mbox{\it GF}(p)$.

1.

Supongamos que $\forall\; x\in F$ se ha calculado $\log_{\alpha} x$. Dado $y\in \mbox{\it GF}(p)$, elegimos $Z\in [\![0,p-2]\!]$ aleatoriamente y calculamos $y_1=y\cdot\alpha^z$. Si y₁ se factoriza completamente con factores en F, es decir, si expresamos

$$y_1 = \prod_{x\in F} x^{\gamma (x)} \mbox{ mod }p$$

entonces

$$\log_{\alpha} y= \left(\sum_{x\in F} \gamma (x) \cdot \log_{\alpha} x -z\right) \mbox{ mod }(p-1)$$

Así pues, expresamos a $\log_{\alpha} y$ en términos de los números $\log_{\alpha} x, x \in F$. Veamos pues cómo calcular a estos últimos.

2.

Cálculo de $\log_{\alpha} x\in \mbox{\it GF}(p)$. Generemos card(F) exponentes $z\in [\![0, p-2]\!]$ tales que $\alpha^z$ se factoriza completamente en F:

$$\alpha^z = \prod_{x\in F} x^{\gamma (z,x)} \mbox{ mod }p.$$

Entonces

$$z= \left(\sum_{x\in F} \gamma (z,x) \cdot \log_{\alpha} x -z\right) \mbox{ mod }(p-1)$$

lo cual dará un sistema (no singular) de card(F) ecuaciones lineales en $\mbox{\it GF}(p)$, con card(F) incógnitas $\{ \log_{\alpha} x \}_{x \in F}$. La dificultad de esta etapa consiste en elegir a los números z. Otro problema es la elección del mismo conjunto F. Un criterio es el siguiente:

3.

Sea $\beta >0$ y sea $B = e^{\beta \sqrt{ \log p \cdot\log \log p }}$. Elijamos $F=\{ x\in \mbox{\it GF}(p)\vert x \mbox{ es un primo y } x<B\}$.

El algoritmo descrito tendrá complejidad en tiempo $O( e^{\gamma \sqrt{ \log p \cdot\log \log p }})$ donde $\gamma$ es una constante.