¿Cómo medir la complejidad del problema de logaritmo discreto?

Las respuestas a esta pregunta en Crypto Stack Exchange básicamente dicen que, para medir la complejidad del problema del logaritmo, debemos tener en cuenta la longitud del número que representa el tamaño del grupo. Parece arbitrario, ¿por qué no elegimos el tamaño del grupo como argumento? ¿Existe algún criterio para saber qué argumento elegir? De hecho, sé que pasé por alto algo importante ya que la complejidad cambia enormemente si lo hacemos por el tamaño del grupo.

time-complexity discrete-mathematics cryptography Nassim HADDAM
fuente

¡Interesante pregunta! Lo edité para decir "medir la complejidad", en lugar de "calcularlo", ya que la respuesta a cómo lo calculamos es ¯ \ _ (ツ) _ / ¯. :-)

David Richerby

Creo que es mejor así. :)

Nassim HADDAM

Respuestas:

$|G|$ $n$ $n \approx \log |G|$ $n$ $|G|$

$n$ $\Theta(n)$
$n$ $1024$ $|G|$ $2^{1024}$

Yuval Filmus
fuente

Veo su punto, pero ¿no es un problema en P si elegimos el tamaño del grupo como parámetro?

Nassim HADDAM

No puede elegir el parámetro en ese caso; el parámetro siempre es la longitud de entrada.

Yuval Filmus

Gracias por las respuestas Tuve un problema con lo que podría pasar si consideramos el otro caso (problemas en que P se convierta en NP y viceversa). Yo puedo ver claramente ahora :) .

Nassim HADDAM

No hacemos el cálculo en unario ya que nuestro objetivo es factorizar algún número o calcular algún logaritmo discreto, y no nos importa cómo se representa el número. Darlo como entrada en binario o unario no afecta el "tiempo de pared" necesario para resolver el problema, solo su complejidad en términos del tamaño de entrada (¡ya que estamos cambiando el tamaño de entrada!).

Yuval Filmus

Además, realmente no podemos tener un número entero de 128 bits como entrada unaria a un algoritmo del mundo real. No hay suficientes átomos en el universo.

Yuval Filmus