Siguiente: En campos finitos Un nivel arriba: En anillos de residuos Anterior: Algoritmo de Shank

Algoritmo de Pohlig-Hellman

Con las notaciones anteriores, supongamos factorizado como un producto de primos $p-1=\prod_{i=1}^{t} p_i^{e_i}$. Como se quiere conocer el exponente $z\mbox{\rm mod }(p-1)$, por el Teorema Chino del Residuo, basta calcular $z\mbox{\rm mod }(p_i)$, $i=1,\ldots,t$. Consideremos pues el siguiente problema:


Instancia:

Solución:




Escribamos a la solución del problema en base q: $z_q=\sum_{i=0}^{e-1} a_i q^i$. Ya que $z=z_q\mbox{\rm mod }q^e$ se tiene z=z_q+sq^e, para algún $s\in I\!\!N$. Observamos que

$$z_q+sq^e-a_0=\sum_{i=1}^{e-1} a_i q^i + sq^e=q\left[\sum_{i=0}^{e-2} a_{i+1} q^i + sq^{e-1}\right]$$

es decir $\frac{1}{q}\left[z_q+sq^e-a_0\right]$ es un entero. Consecuentemente

$$\eta:= \frac{p-1}{q}\left[z_q+sq^e\right]=\frac{p-1}{q}a_0\mbox{\rm mod }(p-1)=:\theta\mbox{\rm mod }(p-1).$$

Por tanto,

$$y^{\frac{p-1}{q}}=x^{\eta}=x^{\theta}.$$

Calculemos pues $v=y^{\frac{p-1}{q}}$. Si v=1 entonces a₀=0. En otro caso, el mínimo i tal que $v=x^{i\frac{p-1}{q}}$ dará el valor de a₀. Si c=1 entonces z_q=a₀. En otro caso, hacemos $y_1=y\cdot x^{-a_0}$. Denotemos por z₁ al exponente tal que $z_1=(\log_x(y_1)\mbox{\rm mod }q^e$. De hecho, $z_1=\sum_{i=1}^{e-1} a_i q^i$. Como antes,

$$y_1^{\frac{p-1}{q^2}}=x^{\frac{p-1}{q}a_1}\mbox{\rm mod }p.$$

Calculemos pues $v_1=y_1^{\frac{p-1}{q^2}}$. Si v₁=1 entonces a₁=0. En otro caso, el mínimo i tal que $v_1=x^{i\frac{p-1}{q}}$ dará el valor de a₁. Si c=2 entonces z_q=a₀+a₁q. En otro caso, se repite el procedimiento.

  

Figure 3.1: Algoritmo de Pohlig-Hellman.

Siguiente: En campos finitos Un nivel arriba: En anillos de residuos Anterior: Algoritmo de Shank