Una cosa que nunca he entendido del todo es por qué el cálculo de logaritmos discretos (en el grupo multiplicativo mod p) y la factorización parecen estar tan estrechamente relacionados. No creo que haya una reducción en ninguno de los dos sentidos, al menos cuando p es primo (aunque una rápida búsqueda bibliográfica me dice que hay una probabilístico reducción en una dirección), pero hay un gran número de similitudes no triviales:
- Se cree que ninguno de ellos tiene un algoritmo clásico de tiempo polinómico, pero esencialmente el mismo algoritmo cuántico funciona para ambos.
- Ambos sirven de base fácil para la criptografía de clave pública, mientras que otros problemas (por ejemplo, los basados en celosías) son mucho más difíciles de convertir en criptosistemas operativos, y algunos (isomorfismo de grafos, cálculo de la permanente) parecen no tener esperanza alguna de ser útiles en criptografía.
- Muchos de los algoritmos clásicos para uno de ellos están estrechamente relacionados con un algoritmo clásico para el otro -- tamiz de campo de números y tamiz de campo de funciones, rhos de Pollard, métodos de paso de bebé a paso de gigante frente a métodos de tipo Fermat, etcétera.
¿Hay alguna razón sencilla por la que, aunque en teoría no son reducibles entre sí, en la práctica se comportan como si lo fueran?
Edición: Para aclarar más, como Rune señala, tanto la factorización como el logaritmo discreto pueden verse como versiones del problema del subgrupo oculto sobre un grupo abeliano. Entiendo por qué hay algoritmos cuánticos para esto, y algunos de los obstáculos a los algoritmos cuánticos para HSP no abelianos, e incluso hasta cierto punto por qué HSP es bueno para basar un sistema de clave pública. Mi pregunta es esencialmente por qué "comparten un vínculo mucho más estrecho que no se ve con otras HSP abelianas".
