Factorización de un número entero en el intervalo dado

Question

Deje que N sea un entero positivo. Hay un eficiente (es decir, probabilístico polinomio tiempo) algoritmo, el cual, en una entrada lo suficientemente grande N, salidas de la totalidad de la factorización de un número entero en el intervalo de $[N - O(\log N), N]$?

Tenga en cuenta que el tiempo de ejecución del algoritmo se mide en $|N| = O(\log N)$.

Extra: La idea es generar un factor entero como cerrado a N como sea posible. Así, es más conveniente disponer de un algoritmo eficiente que, por lo suficientemente grande como N, su salida es un factor entero en el intervalo de $[N - O(\log\log N), N]$.

---

Publicado: http://mathoverflow.net/questions/72076/.

Answer 1

Escribí una Función de Python que se supone que pasaría a ser parte de un entero en el intervalo de

[N, N+log2(N)], que era esencialmente el factor de poder por parte de enteros pequeños.

Mi programa demostrado que, en general, este no es el caso.

René De La Rosa