Factorizando Compuestos

Question

Decimos $N=AB$ donde $A$ y $B$ son números primos. Escribimos: $$A=a+x,\qquad B=a-x.$$ Es decir, $$a=\frac{A+B}{2};\qquad x=\frac{A-B}{2};$$ $A$ y $B$ son números impares. Por lo tanto $A+B$ y $A-B$ son pares. Y $a$ y $x$ son enteros. $$\begin{align*} AB&=(a+x)(a-x);\\ AB&=a^2-x^2\\ N&=a^2-x^2\\ a^2&=N+x^2 \end{align*}$$

Pasos: Encuentra un número cuadrado perfecto, $K$, mayor que $N$ [es decir, tenemos que buscar números cuadrados perfectos que sean mayores que $N$].

Si $K-N=M$ es un cuadrado perfecto:

$A=\sqrt{K}+\sqrt{M}$

$B=\sqrt{K}-\sqrt{M}$

[Ya que $K=a^2$ y $M=x^2$ ; $N=a^2-x^2=K-M$]

$N=A*B$

Ejemplo:

Factorización de $1159[=N]$

$1600$ es un número cuadrado perfecto mayor que $1159$

$$\begin{align*} 1600-1159&=441=21^2\\ K&=1600\\ M&=441\\ A&=40+21=61\\ B&=40-21=19\\ N&=61\times 19=1159 \end{align*}$$

¿Sería este proceso conveniente para un número compuesto [de la forma $N=A*B$, $A$ y $B$ son primos] que tenga 400 dígitos, si se te permite usar un microprocesador?

Answer 1

Originalmente escribí esto como un comentario, pero tal vez debería ser una respuesta.

Este es un método bien conocido conocido como Factorización de Fermat o factorización de Diferencia de Cuadrados. Por sí sola, la factorización de Fermat incluso podría funcionar peor que la división por pruebas (la factorización de Fermat funciona mejor cuando ambos factores primos están cerca uno del otro, y por lo tanto cerca de la raíz cuadrada de $N$; la división por pruebas funciona mejor cuando $N$ tiene un factor primo pequeño).

Combinándolo hábilmente con la división por pruebas utilizando un método de Lehman se obtiene un algoritmo que es aproximadamente $O(N^{1/3})$. Esto no es adecuado para factorizar compuestos del tamaño de RSA (hay algunos compuestos RSA de alrededor de 250 dígitos que aún no han sido factorizados).

La idea detrás de la factorización de Fermat también es parte de la inspiración detrás de los predecesores de la Criba General de Cuerpo de Números que es el algoritmo más eficiente conocido para factorizar números generales.