Método 6: Generalización del método de Fermat (ó método AB)
Saludos, Gaussito. Me uno a tu propuesta de exponer aquí métodos de factorización.
El algoritmo que voy a exponer aquí es una generalización del método de Fermat. Lo desarrollaré tal y como lo fui desarrollando yo, pensando que era un método diferente de otros, pero al final ví que simplemente era una generalización del método de Fermat. La idea me vino de un libro de criptografía, en el que daban una recomendación para generar pares de números primos para aplicarlos al criptosistema RSA. Esta recomendación es nefasta, ya que los números propuestos se pueden factorizar con este método de forma casi inmediata. En lo que sigue, todas las variables son enteras.
Fundamento teóricoPartimos del entero [texx]\displaystyle m[/texx], que queremos factorizar. Podemos escribirlo como [texx]\displaystyle m=r\cdot s[/texx], [texx]\displaystyle r[/texx] y [texx]\displaystyle s[/texx] no necesariamente primos. Sea [texx]\displaystyle r\leq s[/texx]. Podemos escribir [texx]\displaystyle s=a\cdot r+b[/texx], con [texx]\displaystyle 0\leq b<r[/texx] y [texx]\displaystyle a>0[/texx]
Ahora, podemos sustituir [texx]\displaystyle s[/texx] en la expresión [texx]\displaystyle m=r\cdot s[/texx], de forma que nos queda [texx]\displaystyle m=r\cdot (a\cdot r+b) \Rightarrow{m=a\cdot r^2+b\cdot r}[/texx]. Pero esto es una ecuación de segundo grado de la forma [texx]\displaystyle a\cdot r^2+b\cdot r-m=0[/texx], donde [texx]\displaystyle r[/texx] es la incógnita (que es, precisamente, lo que queremos determinar).
De esta ecuación de segundo grado desconocemos los valores de [texx]\displaystyle a[/texx], [texx]\displaystyle b[/texx] y [texx]\displaystyle r[/texx], lo cual parece que ha empeorado el problema. El valor que nos interesa, como dijimos antes, es el de [texx]\displaystyle r[/texx]. Podemos aplicar la fórmula que nos da la solución de la incógnita:
[texx]\displaystyle r=\frac{-b\pm \sqrt{b^2-4\cdot a\cdot (-m)}}{2a}[/texx]
Dado que [texx]\displaystyle r[/texx] es positivo, en la anterior fórmula sólo nos interesa sumar la raíz cuadrada, ya que restarla generaría un valor negativo (pues recordemos que [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son positivos). Así, la solución anterior nos quedará finalmente como:
[texx]\displaystyle r=\frac{-b+\sqrt{b^2+4\cdot a\cdot m}}{2a}[/texx]
Ahora tenemos una igualdad con dos incógnitas, [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx], con las que podemos obtener [texx]\displaystyle r[/texx]. Basta darles a [texx]\displaystyle a[/texx] y a [texx]\displaystyle b[/texx] valores enteros hasta obtener como valor de [texx]\displaystyle r[/texx] un valor entero. Si resulta que [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son pequeñas, podremos encontrar el valor de [texx]\displaystyle r[/texx] en poco tiempo.
Pero este procedimiento se puede mejorar bastante. Puesto que [texx]\displaystyle r[/texx] es entero, y estamos trabajando con enteros, necesariamente la raíz cuadrada debe ser entera, lo que significa que la expresión que hay en su interior debe ser un cuadrado perfecto. Esto lo podemos expresar como [texx]\displaystyle b^2+4\cdot a\cdot m=c^2[/texx], con [texx]\displaystyle c[/texx] entero.
Ahora, tenemos que hallar un valor de [texx]\displaystyle b[/texx] para que [texx]\displaystyle b^2+4\cdot a\cdot m[/texx] sea un cuadrado perfecto. Podríamos irle dando valores, partiendo desde [texx]\displaystyle 0[/texx] en adelante. Pero vamos a hacer una cosa mejor. Vamos a aplicar el mismo principio aplicado en el método de Fermat, y es reescribir la anterior expresión como [texx]\displaystyle b^2=c^2-4\cdot a\cdot m[/texx], e irle dando valores a [texx]\displaystyle c[/texx]. Pero como [texx]\displaystyle b^2[/texx] será [texx]\displaystyle 0[/texx] o positivo, necesariamente tiene que cumplirse que [texx]\displaystyle c^2\geq 4\cdot a\cdot m[/texx] para que su diferencia sea [texx]\displaystyle 0[/texx] o positiva. Pero además, al ir incrementando [texx]\displaystyle c[/texx] de [texx]\displaystyle 1[/texx] en [texx]\displaystyle 1[/texx], resulta que su cuadrado se incrementa bastante más. Es decir, que cada incremento de [texx]\displaystyle c[/texx] se salta muchos valores de [texx]\displaystyle b[/texx] que no valdrían, valores que hubiéramos probado si hubiéramos probado incrementando [texx]\displaystyle b[/texx].
En cada incremento de [texx]\displaystyle c[/texx] hay que comprobar si [texx]\displaystyle c^2-4\cdot a\cdot m[/texx] es un cuadrado perfecto, porque de serlo, resulta que ese cuadrado será el valor de [texx]\displaystyle b^2[/texx], del que podemos extraer el valor de [texx]\displaystyle b[/texx] calculando su raíz cuadrada.
Este valor de [texx]\displaystyle b[/texx], junto con el de [texx]\displaystyle a[/texx], es el que nos proporciona una raíz cuadrada entera en la solución de la ecuación de segundo grado de antes. Ahora tenemos que ver que este valor:
[texx]\displaystyle r=\frac{-b\pm \sqrt{b^2-4\cdot a\cdot (-m)}}{2a}[/texx]
es entero. Porque en principio, nada nos garantiza que la fracción que tenemos sea entera. Pero veremos cómo resolver esto a continuación.
Antes escribimos la expresión [texx]\displaystyle s=a\cdot r+b[/texx]. Pero podemos escribir igualmente esta otra: [texx]\displaystyle s=a'\cdot r-b'[/texx], donde [texx]\displaystyle a'=a+1[/texx] y [texx]\displaystyle b'=r-b[/texx]. Como antes, sustituyendo en la expresión [texx]\displaystyle m=r\cdot s[/texx], nos queda [texx]\displaystyle m=r\cdot (a'\cdot r-b')\Rightarrow{m=a'\cdot r^2-b'\cdot r}[/texx]. Como antes, estamos ante una ecuación de segundo grado: [texx]\displaystyle a'\cdot r^2-b'\cdot r-m=0[/texx]. La solución de [texx]\displaystyle r[/texx] vendrá dada por
[texx]\displaystyle r=\frac{-(-b')\pm \sqrt{(-b')^2-4\cdot a'\cdot (-m)}}{2a'}[/texx]
Desarrollando los signos, queda finalmente:
[texx]\displaystyle r=\frac{b'\pm \sqrt{b'^2+4\cdot a'\cdot m}}{2a'}[/texx]
Sabemos que la raíz cuadrada de esta expresión es mayor que [texx]\displaystyle b'[/texx], ya que en su interior está el valor [texx]\displaystyle b'^2[/texx] más otro valor, lo que significa que la raíz cuadrada será [texx]\displaystyle b'[/texx] más otro valor. Por tanto, si restamos la raíz cuadrada a [texx]\displaystyle b'[/texx], obtendremos un valor negativo para [texx]\displaystyle r[/texx]. Pero [texx]\displaystyle r[/texx] es positivo, por lo que nos tenemos que quedar con la suma de la raíz cuadrada. Es decir, al final tenemos:
[texx]\displaystyle r=\frac{b'+\sqrt{b'^2+4\cdot a'\cdot m}}{2a'}[/texx]
Si observamos, esta expresión sólo difiere de la otra en que [texx]\displaystyle b'[/texx] aquí no tiene signo negativo, y en la otra [texx]\displaystyle b[/texx] sí que tiene signo negativo. Más importante aún es el hecho de que el interior de la raíz cuadrada es el mismo para ambas expresiones. Esto significa que el procedimiento explicado antes para obtener el valor de [texx]\displaystyle b[/texx] es exactamente el mismo que el que tendremos que aplicar aquí, y además, que las soluciones obtenidas para que la raíz cuadrada sea entera serán las mismas. Así, con un mismo procedimiento obtenemos posibles soluciones para dos expresiones. Si una solución no vale para una de las expresiones, quizá valga para la otra. Pero vamos a ver que la primera expresión que encontremos nos va a servir de solución para obtener los valores de [texx]\displaystyle r[/texx] y de [texx]\displaystyle s[/texx].
Tenemos las dos expresiones, en las que utilizaremos los mismos valores para [texx]\displaystyle a[/texx] y para [texx]\displaystyle b[/texx]:
[texx]\displaystyle r=\frac{-b+\sqrt{b^2+4\cdot a\cdot m}}{2a}[/texx]
[texx]\displaystyle r=\frac{b+\sqrt{b^2+4\cdot a\cdot m}}{2a}[/texx]
El problema que tenemos aquí es que no sabemos si, cuando encontremos una solución para [texx]\displaystyle b[/texx], alguna de las anteriores fracciones será entera. Es decir, si será solución para [texx]\displaystyle r[/texx].
Cojamos los numeradores de las fracciones y multipliquémoslos:
[texx]\displaystyle (b+\sqrt{b^2+4\cdot a\cdot m})\cdot (-b+\sqrt{b^2+4\cdot a\cdot m})=\\
b\cdot (-b)+b\cdot\sqrt{b^2+4\cdot a\cdot m}-b\cdot\sqrt{b^2+4\cdot a\cdot m}+\sqrt{b^2+4\cdot a\cdot m}\cdot\sqrt{b^2+4\cdot a\cdot m}=\\
-b^2+b^2+4\cdot a\cdot m=\\
4\cdot a\cdot m[/texx]
Para simplificar, teniendo en cuenta que [texx]\displaystyle c^2=b^2+4\cdot a\cdot m[/texx] (es lo que obtuvimos antes), usaremos el valor de [texx]\displaystyle c[/texx] en lugar del valor [texx]\displaystyle \sqrt{b^2+4\cdot a\cdot m}[/texx]. Por tanto, lo anterior queda como:
[texx]\displaystyle (c+b)\cdot(c-b)=4\cdot a\cdot m[/texx]
Por tanto, tenemos que:
[texx]\displaystyle m=\frac{(c+b)\cdot(c-b)}{4\cdot a}[/texx]
El problema es que puede que [texx]\displaystyle 4\cdot a\nmid c+b[/texx] y [texx]\displaystyle 4\cdot a\nmid c-b[/texx]. Pero lo que sí sabemos es que [texx]\displaystyle 4\cdot a\mid (c+b)\cdot(c-b)[/texx], por lo que basta hacer:
[texx]\displaystyle r=\frac{c+b}{\gcd(4\cdot a,c+b)}[/texx]
[texx]\displaystyle s=\frac{(c-b)\cdot\gcd(4\cdot a,c+b)}{4\cdot a}[/texx]
Así, una vez encontrado un valor de [texx]\displaystyle b[/texx] con el procedimiento explicado, ya podemos obtener una factorización de [texx]\displaystyle m[/texx].
Puede verse que este método es el método de Fermat aplicado al valor [texx]\displaystyle 4\cdot a\cdot m[/texx], con [texx]\displaystyle a[/texx] un valor que elegimos nosotros. Y si [texx]\displaystyle a=1[/texx], simplemente estamos ante el método de Fermat para [texx]\displaystyle 4\cdot m[/texx], el cual será más ineficiente que si lo hiciéramos para [texx]\displaystyle m[/texx].
Como se podrá suponer, lo de llamar este método como "método AB" proviene de que estamos buscando valores para [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx].
Fundamento prácticoAsí, como está, no parece un algoritmo muy práctico. Deberíamos establecer un valor para [texx]\displaystyle a[/texx] y después buscar valores para [texx]\displaystyle b[/texx]. Si nos pasamos con el valor de [texx]\displaystyle a[/texx], podríamos no encontrar la solución.
Pero lo que vamos a hacer es una búsqueda en paralelo o, mejor dicho, varias búsquedas cada vez. Consiste en lo siguiente. En lugar de establecer un valor para [texx]\displaystyle a[/texx], establecemos un conjunto de valores para [texx]\displaystyle a[/texx], comprendidos entre [texx]\displaystyle 1[/texx] y un valor [texx]\displaystyle k[/texx] que consideremos adecuado. Después, aplicamos el algoritmo a cada uno de los valores. Para ello, calculamos los valores que tomará [texx]\displaystyle c[/texx] en cada uno de los valores de [texx]\displaystyle a[/texx] (es decir, calculamos [texx]\displaystyle c=\sqrt{4\cdot a\cdot m}[/texx]. Si es entero, lo almacenamos como está. Si no lo es, obtenemos la parte entera, le sumamos [texx]\displaystyle 1[/texx], y almacenamos el resultado).
Ahora, para cada valor de [texx]\displaystyle a[/texx], comprobamos si [texx]\displaystyle c^2-4\cdot a\cdot m[/texx] es un cuadrado perfecto. Si es así, hemos encontrado los valores [texx]\displaystyle a[/texx] (que será el que estemos utilizando en este momento) y [texx]\displaystyle b[/texx], por lo que podemos obtener una factorización de [texx]\displaystyle m[/texx]. Si no obtenemos ningún cuadrado perfecto para ningún valor de [texx]\displaystyle a[/texx], incrementamos todos los [texx]\displaystyle c[/texx] en [texx]\displaystyle 1[/texx], y repetimos.
Con este método, si [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son pequeños en la expresión [texx]\displaystyle s=a\cdot r\pm b[/texx], con [texx]\displaystyle m=r\cdot s[/texx], encontraremos rápidamente la factorización de [texx]\displaystyle m[/texx].
Este método sólo es eficiente cuando [texx]\displaystyle m[/texx] tiene una expresión de la forma [texx]\displaystyle m=r\cdot s[/texx], [texx]\displaystyle r\leq s[/texx], y en donde la expresión [texx]\displaystyle s=a\cdot r\pm b[/texx] tiene valores pequeños para [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] (bien sea que [texx]\displaystyle b[/texx] esté sumando, o restando). En caso de que [texx]\displaystyle m[/texx] tenga más de una expresión de la forma [texx]\displaystyle m=r\cdot s[/texx], la factorización que encuentre será aquella para la que el valor de [texx]\displaystyle b[/texx] es el más pequeño (tanto si está sumando como si está restando).
El algoritmoÉste es el algoritmo, para que los que lo quieran implementar lo tengan más fácil:
Entrada:
m: Entero a factorizar
k: Número de valores que se le darán a "a", comprendidos entre 1 y el valor especificado
Salida:
r: Uno de los divisores de "m", donde "m=r*s"
s: Otro de los divisores de "m", donde "m=r*s"
Procedimiento:
Definir variable "arrayC" como un array de enteros de "k" elementos
Definir variables "a" y "b" como enteros
Definir variable "i" como entero
Bucle Desde a=1 hasta a=k, hacer:
Hacer arrayC[a]=int(sqrt(4*a*m))
Si arrayC[a]*arrayC[a]=4*a*m
Hacer b=0
Ir a etiqueta "Solución encontrada"
Fin Si
Hacer a=a+1
Fin Bucle Desde
Bucle Repetir Siempre, hacer:
Bucle Desde a=1 hasta a=k, hacer:
Hacer b=int(sqrt(arrayC[a]*arrayC[a]-4*a*m))
Si b*b=arrayC[a]*arrayC[a]-4*a*m
Ir a etiqueta "Solución encontrada"
Fin Si
Hacer arrayC[a]=arrayC[a]+1
Hacer a=a+1
Fin Bucle Desde
Fin Bucle Repetir Siempre
Etiqueta "Solución encontrada":
Hacer r=(arrayC[a]+b)/mcd(4*a,arrayC[a]+b)
Hacer s=(arrayC[a]-b)*mcd(4*a,arrayC[a]+b)/(4*a)
Devolver "r" y "s"
Fin Procedimiento
Se puede mejorar el algoritmo haciendo un test de cuadrados en el valor "arrayC[a]*arrayC[a]-4*a*m", en lugar de calcular su raíz cuadrada entera y luego viendo si el cuadrado del valor calculado coincide con "arrayC[a]*arrayC[a]-4*a*m". Para enteros grandes esto puede acelerar bastante las cosas si el test de cuadrados es rápido. Lamentablemente este algoritmo no sirve para enteros grandes salvo que se den las condiciones necesarias para que factorice en un tiempo razonable.
Espero no haberme equivocado en nada
Una varianteHace tiempo que leí que cuando no se dan las condiciones para factorizar en un tiempo razonable el entero [texx]\displaystyle m[/texx] con el método de Fermat, a veces pueden mejorarse estas condiciones intentando factorizar [texx]\displaystyle k\cdot m[/texx], donde [texx]\displaystyle k[/texx] sería un entero que deberíamos elegir nosotros. El problema es qué entero elegir.
Esto mismo puede aplicarse a este algoritmo. Puede ocurrir que tengamos enteros [texx]\displaystyle u[/texx] y [texx]\displaystyle v[/texx] tales que, si [texx]\displaystyle m=r\cdot s[/texx] no es fácilmente factorizable con este algoritmo, puede que sí lo sea si hacemos [texx]\displaystyle m=(r\cdot u)\cdot(s\cdot v)[/texx], donde [texx]\displaystyle r\cdot u\leq s\cdot v[/texx] y [texx]\displaystyle s\cdot v=a\cdot r\cdot u+b[/texx]. Es fácil demostrar que este caso sí se puede dar. Simplemente reescribimos lo anterior como [texx]\displaystyle s\cdot v-a\cdot r\cdot u=b[/texx], y vemos que es una ecuación diofántica cuyas incógnitas son [texx]\displaystyle u[/texx] y [texx]\displaystyle v[/texx], suponiendo conocidos [texx]\displaystyle r[/texx] y [texx]\displaystyle s[/texx], y especificados de forma casi arbitraria [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] ("casi arbitraria" porque tienen que cumplir las condiciones para que tenga solución la ecuación).
El problema es que no conocemos [texx]\displaystyle r[/texx] ni [texx]\displaystyle s[/texx], y tampoco sabemos qué valores darle a [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx]. Lo único que podemos hacer es probar a multiplicar [texx]\displaystyle m[/texx] por otro entero [texx]\displaystyle n=u\cdot v[/texx], y aplicar el algoritmo, a ver si hay suerte. No necesitamos determinar qué valores toman [texx]\displaystyle u[/texx] y [texx]\displaystyle v[/texx], porque el algoritmo, si encuentra una solución, será aquella para la que [texx]\displaystyle b[/texx] es el más pequeño valor que nos da una solución. Una vez encontrada una solución, habrá que eliminar los factores de [texx]\displaystyle n[/texx] de la misma.
El problema que presenta esta variante es que podemos conseguir el efecto contrario, es decir, que el entero que obtenemos para factorizar sea más difícil de factorizar con este algoritmo que el entero original. Por otro lado, puede ocurrir que la factorización que consigamos no nos dé información de los factores de [texx]\displaystyle m[/texx], sólo de los de [texx]\displaystyle n[/texx], que no son los que buscamos (es decir, podemos obtener como factores [texx]\displaystyle n[/texx] y [texx]\displaystyle m[/texx], o [texx]\displaystyle u[/texx] y [texx]\displaystyle v\cdot m[/texx], etc).
Se me había ocurrido que, cuantos más divisores tenga el entero a factorizar, más probable es que existan enteros [texx]\displaystyle r[/texx] y [texx]\displaystyle s[/texx] que cumplan las condiciones para factorizar rápidamente con este algoritmo. Así que se me ocurrió que podríamos multiplicar [texx]\displaystyle m[/texx] por un factorial, de forma que tendríamos que factorizar el entero [texx]\displaystyle k!\cdot m[/texx], que tendrá tantos más divisores cuanto mayor sea [texx]\displaystyle k[/texx]. Lo he probado y no parece mejorar mucho la cosa. Es más, parece que empeora.
Dejo esta idea por si a alguien le da nuevas ideas que mejoren éste u otros algoritmos de factorización.