Problemas (criptográficos) solucionables en un número polinómico de pasos aritméticos

9

En el artículo de Adi Shamir [1] de 1979, muestra que la factorización se puede hacer en un número polinómico de pasos aritméticos . Este hecho fue reiterado, y por lo tanto me llamó la atención, en el reciente artículo de Borwein y Hobart [2] en el contexto de los programas de línea recta (SLP).

Como me sorprendió bastante leer esto, tengo la siguiente pregunta: ¿Hay algún otro problema criptográfico o tal vez también otros problemas relevantes que puedan resolverse en un número polinómico de pasos con un SLP y que actualmente no se sepa que sean solucionables? eficientemente en una computadora clásica "normal"?

[1] Adi Shamir, Factorización de números en pasos aritméticos O(Iniciar sesión⁡norte) . Cartas de procesamiento de información 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs , The American Mathematical Monthly Vol. 119, núm. 7 (agosto ‒ septiembre de 2012), págs. 584-592

cc.complexity-theory cr.crypto-security algebraic-complexity Etsch
fuente
¿Qué significa "solucionable en número polinómico de pasos aritméticos"? Los mejores algoritmos de factorización disponibles actualmente toman tiempo subexponencial (pero superpolinomial). No puedo encontrar el papel de Shamir en ningún lado.
mikeazo
Sugeriría publicar esto en Crypto.SE ya que no ha recibido mucha respuesta aquí.
mikeazo
Hay una entrada de blog relacionada de Lipton: rjlipton.wordpress.com/2012/10/16/… Este modelo de computación es una especie de trampa, porque está permitiendo cálculos con precisión arbitraria y larga. No conozco otros problemas relacionados con la criptografía que se hayan abordado en este modelo. Pero el modelo es tan poderoso que valdría la pena intentarlo.
minar
@minar el problema de trampa no es con precisión de aribtrary. el engaño aquí es con operaciones de piso y techo.
T ....

Respuestas:

-2

No leí el documento también, pero el resumen parece decir que se requiere un número exponencial de operaciones de bits.

El trabajo de Chebyshev sobre congruencias y su reformulación en el algoritmo AKS muestran que la generación principal está en P. Por lo tanto, la división de prueba produce factores no triviales. En ese caso, para algún número N, puede esperar una densidad de primos de 1 / ln (N).

Además, puede echar un vistazo a la tesis doctoral de Turing de 1937 sobre el tema.

Phil
fuente
3
Hola Phil Bienvenido a cstheory. Has estado publicando respuestas a muchas preguntas en poco tiempo, lo cual no es habitual aquí. Las publicaciones que realmente son comentarios y no respuestas a la pregunta no deben publicarse como respuestas. Es posible que desee mirar alrededor y consultar otras preguntas y cómo funcionan las cosas aquí antes de publicar más respuestas.
Kaveh