Estoy siguiendo el comentario de DanielV, que usted no entiende. DanielV dijo:
Si hubo un polytime forma de factor de un número dado la factorización de un vecino, entonces sería trivial factor en polytime, porque sólo podría factor de forma recursiva $\frac{N±1}{2^k}$ por lo que mayor $k$, se obtiene un número entero.
Nuestra hipótesis es que existe un algoritmo $M$, lo que lleva a la factorización de $n\pm 1$ y eficiente devuelve la factorización de $n$. Vamos a ver cómo la existencia de $M$ nos permite rápidamente factor 1005973.
Ambos 1005973+1 y 1005973-1 son aún, y uno de ellos debe ser un múltiplo de 4. Podemos determinar rápidamente que 1005972=4·251493. Así que nos gustaría factor 251493; si pudiéramos factor 251493, nos gustaría añadir $2^2$ a la factorización, dar el resultado a $M$, y, a continuación, $M$ devolvería la factorización de 1005973 que queríamos.
Pero 251493 es mucho menor que 1005973, y utilizando el mismo método, se puede reducir el problema de la factorización 251493 a la de la factorización de un número aún menor.
Usando el mismo método, se determina que:$$\begin{array}{rl} 251492 &= 4\cdot62873\\
62872 & = 8\cdot7859 \\
7860 &= 4·1965 \\
1964 &= 4\cdot491 \\
492 &= 4·123 \\
124 &= 4·31
\end{array}$$
Podríamos seguir, pero voy a suponer que la factorización prima de 31 es conocido, para no insistir sobre el punto.
Ahora tenemos una factorización prima para 124, por hipótesis, se puede dar esta a $M$, que rápidamente nos dicen que la factorización prima de 123. A partir de esto es trivial para la construcción de la factorización en primos de 4·123, porque es la misma pero con un extra de $2^2$. Damos este a $M$ para obtener la descomposición en factores primos de 491, que es casi la misma que la factorización en primos de 4·491 = 1964, que se puede dar a $M$ para obtener la descomposición en factores primos de 1965. Vamos a proceder de esa manera hasta la mesa hasta que $M$ nos da la factorización prima de 251493; anexando $2^2$ a esta factorización, obtenemos la factorización de 1005972=4·251493, que, dado a $M$, produce la factorización de nuestro número original 1005973.
Cada paso implica una pequeña cantidad de trabajo (un par de divisiones por 2, más un poco de la teneduría de libros), además de una llamada a $M$; el número de pasos es evidentemente limitada por arriba por $\log_4 N$. Así que el tiempo de ejecución de la totalidad del algoritmo es $O(\log_4(N) \cdot m(N))$ donde $m$ es el tiempo de ejecución de $M$. Si $m(N)$ es el polinomio en $N$, por lo que es todo el algoritmo.
Si $M$ es más limitada, dicen que sólo se puede producir la factorización de $N+1$, no $N-1$, dada la factorización de $N$, el número de pasos en la mayoría de los dobles, a $\log_2 N$.
