La dificultad de logaritmo discreto dependen de la dificultad de la factorización de enteros?

Question

La seguridad de muchos (la mayoría? todos?) criptografía de clave pública de los sistemas se basan en la dificultad del logaritmo discreto o de la factorización de enteros. Son estos dos problemas relacionados?

Con el problema del logaritmo discreto me refiero al siguiente problema:

Deje $G$ ser un grupo y vamos a $g$ $h$ ser elementos de $G$ tal que $h \in \langle g \rangle$. Encontrar un entero $x$ tal que $g^x = h$.

En particular, estoy interesado en el caso de que $G = \mathbb{Z}_p^*$. Si sabemos que una manera eficiente de factor de enteros, ¿nos ayudan en la solución del problema del logaritmo discreto para un determinado $\mathbb{Z}_p^*$?

Por el contrario, si sabemos cómo resolver el problema del logaritmo discreto de manera eficiente para cualquier grupo de $G$ (o $\mathbb{Z}_p^*$), hace de esta ayuda con la factorización de números enteros?

Answer 1

Son estos dos problemas relacionados?

La respuesta es sí, y es en muchos niveles. El general de campo de número de tamiz, que es generalmente considerado como un algoritmo de factorización, también es muy útil para problemas discretos registros.

Teóricamente: La resolución de la discreta registro con un compuesto de módulo es exactamente tan duro como el factoring [3]. Sin embargo, no se sabe si la solución discreta de registro con un primer módulo conduce a la eficiencia de factoring [4].

Si sabemos que una manera eficiente de factor de enteros, ¿nos ayudan en la solución del problema del logaritmo discreto para un determinado $\mathbb{Z}_p^*$?

Por el contrario, si sabemos cómo resolver el problema del logaritmo discreto de manera eficiente para cualquier grupo G (o $\mathbb{Z}_p^*$), hace de esta ayuda con la factorización de números enteros?

Para el compuesto módulo, la respuesta es sí. Para el primer módulo, no lo sabemos.

Una buena referencia para una gran cantidad de esta información es John Gregg tesis de la página 43.