¿Referencia para el algoritmo de factorización óptimo de Levin?

En el " Consejo para un estudiante graduado principiante " de Manuel Blum :

LEONID LEVIN cree mientras hago eso, sea cual sea la respuesta a la P = NP? problema, no será como todo lo que crees que debería ser. Y ha dado algunos ejemplos maravillosos. Por un lado, ha dado un ALGORITMO DE FACTORIZACIÓN que es probablemente óptimo, hasta una constante multiplicativa. Él demuestra que si su algoritmo es exponencial, entonces cada algoritmo para FACTORING es exponencial. De manera equivalente, si algún algoritmo para factorizar es poli-tiempo, entonces su algoritmo es poli-tiempo. Pero no hemos podido determinar el tiempo de ejecución de su algoritmo porque, en un sentido fuerte, su tiempo de ejecución es inanalizable.

La página de publicaciones de Levin devuelve un 404, DBLP no muestra nada relacionado con la factorización, y una búsqueda de "factorización de leonid levin" en Google Scholar no devuelve nada de interés que pueda encontrar. AFAIK, el tamiz generalizado es el algoritmo más rápido conocido para la factorización. ¿De qué está hablando Manuel Blum? ¿Alguien puede vincularme a un documento?

ds.algorithms reference-request factoring Christopher Monsanto
fuente

Respuestas:

Manuel Blum está hablando de aplicar el algoritmo de búsqueda universal de Levin al problema de Factorización de enteros. La idea del algoritmo de búsqueda universal de Levin es igualmente aplicable a cualquier problema en la . $NP$

Aquí hay una cita de las notas de conferencias dadas por Blum sobre SEGURIDAD y CRIPTOGRAFÍA:

Leonid LEVIN's OPTIMAL NUMBER-SPLITTING (FACTORING) ALGORITHM. Deje que SPLIT denote cualquier algoritmo que calcule INPUT: un entero compuesto positivo (es decir, no primo) n. SALIDA: un factor no trivial de n.

TEOREMA: Existe un algoritmo de división de números "óptimo", que llamamos OPTIMAL-SPLIT. Este algoritmo es OPTIMAL en el sentido de que: por cada Algoritmo SPLIT de división de números hay una constante (bastante grande pero fija) C tal que para cada entrada entera compuesta positiva n, el "tiempo de ejecución" de OPTIMAL-SPLIT en la entrada n es como máximo C veces el tiempo de ejecución de SPLIT en la entrada n.

Aquí está el algoritmo de factorización óptimo de Levin :

El algoritmo de división óptima: comenzar Enumerar todos los algoritmos en orden de tamaño, lexicográficamente dentro de cada tamaño. Ejecute todos los algoritmos para que, en cualquier momento, t, el algoritmo i-ésimo obtenga [1 / (2 ^ i)] fracción del tiempo de ejecución. Siempre que un algoritmo se detenga con algún número entero de salida m en el rango 1 <m <n, verifique si m divide n (es decir, si n mod m = 0). Si es así, regrese m. FINAL

Mohammad Al-Turkistany
fuente

¿Alguien puede explicar por qué la fracción debe ser 1 / (2 ^ i) pero no algo más simple como 1 / i?

netvope

@netvope: La suma infinita de 1 / i diverge. Es posible que pueda hacerlo con 1 / i ^ 2 pero 1/2 ^ i es mucho más simple.

Antimonio

$NP \cap coNP$

Dado un número, queremos factorizar N.

¿Es N prime? Si es así, salida 'PRIME' más:

$i = 1...\infty$

$P = 1...i$

Ejecute el programa P para i pasos con la entrada N

$L \neq 1$ $M \neq 1$ $N = L*M$ $(L,M)$

Artem Kaznatcheev
fuente

No puede usar una prueba de primalidad conocida porque no se sabe que sea más rápida que la factorización óptima. Además de esto, no entiendo un punto. Para demostrar que esto es óptimo para factorizar hasta un factor constante, creo que tenemos que demostrar que la multiplicación en el último paso no es el término dominante en la complejidad del tiempo. Si no recuerdo mal, el algoritmo de multiplicación más rápido conocido en la configuración asintótica se basa en la FFT y toma O (n log n log log n) tiempo para enteros de n bits. ¿Es posible demostrar que la factorización óptima lleva al menos tanto tiempo como esto?

Tsuyoshi Ito

@ Tsuyoshi: Creo que tienes razón en que este algoritmo no es óptimo si las pruebas de multiplicación / primalidad conocidas son más difíciles que la factorización. Sin embargo, si lees la cita de Blum anterior, solo dice que el algoritmo de Levin es polinómico si y solo si es el óptimo, lo que soluciona este problema. Otras dos cosas: (1) ¿cómo podría evitar usar una prueba de primalidad conocida en este algoritmo? (2) Creo que este algoritmo no está formulado del todo bien porque el tiempo de ejecución no está particionado correctamente entre los diferentes programas; vea la respuesta de Al-Turkistany para la formulación correcta.

Peter Shor

@Peter: Bueno, la cita de Blum dice "él [Levin] ha dado un ALGORITMO DE FACTORACIÓN que es demostrablemente óptimo, hasta una constante multiplicativa". Pero teniendo en cuenta que ni siquiera sabemos si la factorización lleva más tiempo lineal o no, la declaración es difícil de creer como es.

Tsuyoshi Ito

@ Tsuyoshi: Ya veo, estaba leyendo la cita incorrecta de Blum.

Peter Shor