Factorización entera a través de la reducción de celosía?

Encontré un artículo titulado " Factorizando enteros y calculando logaritmos discretos mediante aproximación diofantina " por CP Schnorr de 1993. Parece un método probabilístico con tiempo de ejecución polinomial esperado (y espacio) para realizar la factorización de enteros.

Del documento: "Un escenario para factorizar ... El problema de red correspondiente no es factible para los algoritmos de reducción de red actualmente conocidos. No tenemos experiencia con la reducción de base de red para redes con dimensión 6300. Además, la longitud de bits de los vectores de entrada son al menos 1500. "$N \approx 2^{512}$

Supongo que esto significa que el algoritmo presentado es polinómico, pero el exponente y los factores son tan grandes que lo hace poco práctico para la tecnología actual.

¿Alguien puede opinar sobre esto? ¿Es legítimo este documento? ¿No es una gran noticia si lo es? ¿No significa esto que la factorización entera es probable en P? ¿Ha progresado la gente para hacer que los algoritmos de reducción de red sean más manejables?

$\gamma$

$\gamma$

Arora, et al ( PDF ), muestran que aproximar el vector más cercano dentro de cualquier constante es NP-duro.

$\epsilon > 0$$2^{\log^{\frac{1}{2} - \epsilon}{n}}$

Dinur, et al ( Cita de ACM ), más tarde fortalecieron el resultado de aproximación a:

$\epsilon > 0$$n^{\frac{\epsilon}{\log\log{n}}}$

Aunque no estoy familiarizado con el trabajo de Schnorr, lo que sabemos de los problemas de red me llevaría a creer que esto no pretende conducir directamente a un algoritmo de tiempo polinómico. Por el contrario, Schnorr pasa mucho tiempo hablando de implementaciones reales (por ejemplo, ejecutar este programa en tal y tal computadora lleva aproximadamente tantas semanas / meses / años / eones).

PD Como señala Suresh, parece ser un esfuerzo obtener tiempos de ejecución "lo suficientemente rápidos" o "más rápidos" para la factorización de enteros, a pesar de la complejidad.

PPS Y si puedo hacer una conjetura adicional: dado que el documento de Schnorr es anterior al trabajo sobre la dureza de los problemas de red aproximados, es probable que haya alguna esperanza original de que haya llevado a un algoritmo de tiempo polinómico para la factorización de enteros. A la luz de Arora et al y Dinur et al, sin embargo, está claro que no hay una solución (o al menos, una solución directa) a lo largo de esa ruta.

El documento presenta una reducción del factoring a un problema de red. No se afirma que el problema de la red se pueda resolver en tiempo polinómico (probabilístico). Según tengo entendido, la afirmación de Schnorr es que las implementaciones rápidas para encontrar vectores cortos en redes (estudiadas independientemente, como LLL, etc.) pueden emplearse para implementaciones rápidas de soluciones de factorización (similar en espíritu a cómo los solucionadores de SAT a menudo se pueden usar como una solución rápida). subrutina para resolver otros problemas difíciles)