Cómo determinar en el polinomio de tiempo si un número es un producto de dos números primos consecutivos?

Question

Cómo determinar en el polinomio de tiempo si un número es un producto de dos números primos consecutivos?

Todo lo que puedo averiguar es que si Cramér la conjetura es verdadera, entonces podemos usar la primalidad AKS prueba para encontrar $p_i < \sqrt n < p_{i+1}$, a continuación, compruebe si $p_i * p_{i+1} = n$. Hay alguna manera para determinar si un número es de esta forma en el polinomio de tiempo que no depende de ningún hipótesis no comprobadas?

También, dado que un número es de esta forma, ¿cuál es la manera más rápida de factor? ¿Que tan rápido moderno de propósito general de factoring algoritmos tales como la criba cuadrática factor de un producto de números primos consecutivos?

Answer 1

así que todo depende de la diferencia entre los dos números primos consecutivos. Para el doble de los números primos, es muy fácil, pero para los dos primos con una brecha de 10^10,000 supongo que es mucho más difícil.

Answer 2

Si $\rm\ n = p\:q\ $ es un producto de dos "cerca" de los números primos, es decir, $\rm\:|p-q| < n^{1/3},\:$ $\rm\:n\:$ puede ser factorizado en el polinomio de tiempo, véase Robert Erra; Christophe Grenier. La factorización de Fermat método revisited. 2009. Vea también las diapositivas de Cómo calcular las claves RSA? El Arte de la RSA: Pasado, Presente, Futuro.

Answer 3

Deje $x =\lceil \sqrt{n} \rceil$. Compruebe si $x^2 - n$ es un cuadrado. Si $x^2 - n = y^2$, compruebe si $x+y$ $x-y$ son primos, mediante una adecuada prueba de primalidad. Si es así, comprobar si existen números primos entre $x-y$$x+y$.

Esto también depende de Cramer es una conjetura, por supuesto.

Editar (7/24): Vamos a $n = pq = (x+k)(x-k)$ donde $p,> q$. Ese método es calcular los $\sqrt{n+k^2}$ muchas $k$ hasta que uno encuentra un número entero. A continuación, establezca $x = \sqrt{n+k^2}$$p = x+k, \, q = x-k$.

Para ver cómo esto puede ser acelerado, el uso de la aproximación de Taylor $$ \sqrt{n+k^2} = \sqrt{n} \sqrt{1 + \frac{k^2}{n}} \approx \sqrt{n} \left( 1+ \frac{k^2}{2n}\right) = \sqrt{n} + \frac{k^2}{2\sqrt{n}} $$ a ver que si $\frac{k^4}{n}$ es pequeño, entonces la $0 < \sqrt{n+k^2} - \sqrt{n} < 1$ o así, y simplemente redondeo de $\sqrt{n}$ producirá $k$ inmediatamente, en un solo paso. Ese es el origen de la afección $k \le c n^{1/4}$ que aparece en otro lugar en las respuestas. Esto puede funcionar sólo cuando estamos buscando una factorización en cerca de dos factores. Si funciona para un determinado extraño $n$, se producirá una factorización en dos factores cuya diferencia es mínima y en menos que $2cn^{1/4}$, y que sólo va a trabajar para $n$.

Answer 4

El más rápido de la factorización de método es el Campo de Número de Tamiz (NFS). Para un factor de 1024 bits entero $N$, se tarda alrededor de $2^{86}$ muchos pasos.