¿Qué tan difícil es encontrar el logaritmo discreto?

20

El logaritmo discreto es lo mismo que encontrar en , dada , , y . $b$ $a^b=c \bmod N$ $a$ $c$ $N$

Me pregunto en qué grupos de complejidad (por ejemplo, para computadoras clásicas y cuánticas) se encuentra, y qué enfoques (es decir, algoritmos) son los mejores para realizar esta tarea.

El enlace de wikipedia anterior realmente no ofrece tiempos de ejecución muy concretos. Espero algo más parecido a cuáles son los métodos más conocidos para encontrarlos.

algorithms complexity-theory time-complexity discrete-mathematics Matt Groff
fuente

No sé cuál es el mejor algoritmo, pero puedes encontrar algunos algoritmos en el capítulo 5 de las notas de esta conferencia de Johan Hastad. Resumiría estos algoritmos, pero no leí este capítulo, así que solo proporciono el enlace;)

Marc Bury

21

Respuesta corta.
Si formulamos una versión adecuada del problema de decisión del problema de Logaritmo discreto, podemos mostrar que pertenece a la intersección de las clases de complejidad NP , coNP y BQP .

Una versión de problema de decisión de Discrete Log.
El problema del logaritmo discreto se formula con mayor frecuencia como un problema de función , asignando tuplas de enteros a otro entero. Esa formulación del problema es incompatible con las clases de complejidad P , BPP , NP , etc., que las personas prefieren considerar, que se refieren solo a problemas de decisión (sí / no). Podemos considerar una versión de problema de decisión del problema de registro discreto que es efectivamente equivalente:

Registro discreto (problema de decisión). Dado un primo , un generador de las unidades multiplicativas módulo , un entero y un límite superior , determinan si existe tal que . $N$ $a \in \mathbb Z_N^\times$ $N$ $0 < c < N$ $b \in \mathbb N$ $1 \leqslant L \leqslant b$ $a^L \equiv c \pmod{N}$

Esto nos permitiría calcular realmente el registro _a ( c ) módulo N mediante búsqueda binaria, si pudiéramos resolverlo eficientemente. Entonces podemos preguntar a qué clases de complejidad pertenece este problema. Tenga en cuenta que lo hemos formulado como un problema prometedor: podemos extenderlo a un problema de decisión al suspender los requisitos de que sea primo y un generador, pero agregando la condición que cumplen estas restricciones para cualquier instancia 'SÍ' del problema. $N$ $a \in \mathbb Z_N^\times$

El registro discreto está en BQP.
Usando el algoritmo de Shor para calcular el logaritmo discreto ( Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica ), podemos contener fácilmente el Discreto Log en BQP . (Para probar si es realmente un generador, podemos usar el algoritmo de búsqueda de orden de Shor en el mismo documento, que es la base del algoritmo de logaritmo discreto, para encontrar el orden de y compárelo con .) $a \in \mathbb Z_N^\times$ $a$ $N-1$

El registro discreto está en NP ∩ coNP.
Si en realidad es el caso de que es primo y es un generador, un certificado suficiente para una instancia 'SÍ' o 'NO' del problema de decisión es el entero único tal que . Por lo tanto, es suficiente para demostrar que podemos certificar si las condiciones de y bodega. Siguiendo la nota A de Brassard sobre la complejidad de la criptografía , si es tanto el caso de que es primo como es un generador, entonces es el caso que $N$ $a \in \mathbb Z_N^\times$ $0 \leqslant L < N-1$ $a^L \equiv c \pmod{N}$ $a$ $N$ $N$ $a \in \mathbb Z_N^\times$

r^{N - 1} \equiv 1 (\mod N) and r^{(N - 1) / q} ≢ 1 (\mod N) for primes q dividing N - 1

$r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$}$ por definición (usando el hecho de que tiene el orden ).

Z_{N}^{\times}

$\mathbb Z_N^\times$

N - 1

$N-1$

Un certificado que las limitaciones de y tanto espera sería una lista de los factores primos división , lo que nos permitirá poner a prueba los límites de congruencia anteriores. (Podemos probar si cada es primo usando la prueba AKS si lo deseamos, y probar que estos son todos los factores primos de al intentar encontrar la factorización de potencia prima de solo con esos primos). $N$ $a$ $q_1, q_2, \ldots$ $N-1$ $q_j$ $N-1$ $N-1$
Un certificado de que una de las restricciones en o error sería un número entero que divide , de modo que . No es necesario probar para la primacía en este caso; implica inmediatamente que el orden de es menor que , por lo que es un generador del grupo multiplicativo solo si no es primo. $N$ $a$ $q$ $N-1$ $a^{(N-1)/q} \equiv 1 \pmod{N}$ $q$ $a$ $N-1$ $N$

Niel de Beaudrap
fuente

3

En el escenario general y en el peor de los casos, la respuesta de Niel de Beaudrap es correcta, que yo sepa.

Sin embargo, en el caso de que tenga solo factores primos pequeños, el algoritmo de Pohlig-Hellman encuentra el logaritmo en el tiempo . Por lo tanto, para este caso, el problema Discrete Log es en . Como tal, cuando un protocolo criptográfico depende de la dureza de este problema, es importante elegir el módulo, , de modo que tenga factores primos grandes. $N-1$ $O(log^2(N))$ $P$ $N$ $N-1$

danxinnoble
fuente

-1

desde , entonces . (Lo que significa que la fuerza bruta está en EXP.) $|a|=O(N)$ $b=O(N)$

Para una máquina no determinista, hay un testigo polinomial ya que podemos hacer exponenciación modular en P. (Es decir, el problema está en ). $NP$

La teoría de que los logaritmos discretos están en pero no en es la base de la criptografía moderna, pero eso obviamente no está probado. $NP$ $P$

El método de Shor (vinculado a esa página de wikipedia) se ejecuta en tiempo polinómico en una computadora cuántica.

Xodarap
fuente

¿Qué tan difícil es encontrar el logaritmo discreto?

Respuestas: