La factorización de Fermat siempre se ha presentado como una técnica para representar un número impar como producto de dos de sus factores sin usar la lista de números primos. No es el único algoritmo de factorización con esa propiedad. Si extraemos progresivamente el factor más pequeño (mayor que 1) de N aseguraremos que hemos encontrado un número primo sin tener que memorizar la lista de primos (busca la herramienta factores en la dirección http:/www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm y estudia su funcionamiento).
En efecto, la factorización de Fermat no se basa en los factores primos, sino en representar un número impar N como una diferencia de dos cuadrados y después expresar la misma como el producto de una suma por una diferencia, con lo que se logra la factorización:
N=y2- x2=(x+y)(y-x)
En el caso impar esta operación siempre es posible, porque N=(N+1)2/4-(N-1)2/4, que da lugar a la factorización N=N.1
Desde el punto de vista algorítmico, la búsqueda de los valores de x e y adecuados presenta también otra originalidad, y es que se puede organizar de forma bastante eficiente sólo con sumas y comparaciones. En realidad, todos los algoritmos se pueden organizar así, y en caso último mediante la máquina de Turing, pero tampoco hay que llegar tan lejos. En la búsqueda de la factorización de Fermat se logran resultados bastante aceptables. Es una tortuga, pero algo veloz.
La creación del algoritmo se basa en estos hechos que te pedimos intentes justificar:
(1) El valor de y, y por tanto el de x, están acotados, y su cota no está excesivamente alejada de n ¿Cuál es y cómo se demuestra?
(2) Para demostrar que un número es cuadrado perfecto, no es necesario dividir ni extraer la raíz cuadrada ¿Cómo se hace?
(3) En realidad, la factorización de Fermat consiste en darle al número impar la figura de escuadra simétrica (gnomon) de varias formas posibles. Observando la imagen puedes resolver las dos primeras cuestiones.
(4) Podemos encontrar la raíz cuadrada entera de un número haciendo crecer de forma simultánea dos sucesiones, una linealmente y otra de forma cuadrática. Esto parece obvio, pero ¿cómo se organiza?
Podemos representar el algoritmo como una carrera, liebre y tortuga, entre a=x2 y b=y2, en la que la tortuga sale con ventaja porque se suma al número N, ya que ha de ser y2=x2+N. Todo esto suena a metáfora, pero funciona.
Daremos a continuación un desarrollo en el que se ocultarán algunos detalles para hacer pensar un poco a quien lo siga.
Obtención de un primer valor de a=y2
Las iniciamos a y=1; a=1; i=1
Mientras a no sobrepase a N hacemos crecer estas variables así: y=y+1; i=i+2; a=a+i
con lo que lograremos el primer cuadrado que es mayor o igual que N
Sólo hemos usado sumas y una comparación. Razona por qué se da este resultado.
Obtención de valores adecuados de a=y2 y de b=x2
Una vez obtenido y2 iniciamos el crecimiento de la misma forma para x2
x=1; b=1; j=1
Mientras N+b no sobrepase a y2, hacemos crecer las variables:
x=x+1; j=j+2; b=b+j
para formar el cuadrado x2
Si ocurre que N+b=a hemos conseguido una factorización, pues N=y2-x2
Obtenemos todas las coincidencias
Ya sólo queda hacer crecer a y b de la misma forma y comprobar si se da la igualdad N+b=a en más ocasiones, y así hasta la cota.
No hemos querido usar el lenguaje algorítmico, y se han ocultado algunos detalles, como qué hacer si N es un cuadrado perfecto. Lo importante de lo explicado es que sólo hemos sumado y comparado. No se ha recurrido a multiplicar, dividir o extraer la raíz cuadrada.
Puedes estudiar más a fondo el algoritmo en las hojas de cálculo factorfermat.ods y factorfermat.xls, contenidas en el archivo http:/www.hojamat.es/blog/factorfermat.zip
Si recorres el código de la macro usada, sólo verás operaciones de sumar. El proceso no es un prodigio de velocidad, pero esto es un divertimiento. La idea de hoy no era correr, sino demostrar una posibilidad. Tampoco corrió Fermat y hay que ver lo que logró.
2 comentarios:
Este método es muy bueno no en bruto sino por los secretos que encierran sus variantes. Si este método funciona muy bien cuando los factores están cercanos a la raíz se puede forzar que así sea.
(p+q)/2 = x ; (p-q) = y ---> x^2 - n = y^2 V (x-y)(x+y) = p*q = n
Entonces;
(pk+q)/2 = x´; (pk-q)/2 = y´ --->
x^2 -nk = y^2 ---> mcd(x-y,n) = p
El valor de "k" es desconocido pero sabes que el mejor de los casos tiene que ser y = 1
x^2 - nk = 1 ---> nk+1 = y^2 V y-/+1 no divida a n, o sea x^2 = 1 mod n V x ≠ -/+1 mod n
Entonces el problema de la factorización se simplifica en encontrar el primer múltiplo de un número tal que al añadirle la unidad forme un cuadrado perfecto.
nx+1 = y^2 con y < n-1 siempre cumple esa condición
Tenemos este curioso ejemplo;
100.895.598.169(4)(8) + 1 = 100.895.598.169(32)+1 = 1.796.847^2
mcd(1.796.846,100.895.598.169) = 898.423
Como puede verse cuando el factor de un número es múltiplo del primero más o menos la unidad por forma general que tenga puede factorizarse en O log(n) con una pequeña variante del método de Fermat.
Incluso cuando no tiene forma específica, puede verse que nk = 0 mod 4,buscando 4nk´+1 = y^2 puede encontrarse rápidamente un factor de ´n´ en muchos casos especiales.
El método de factorización de Fermat es brillante en su esencia porque encuentra la media y diferencia entre factores y eso es lo que tarde o temprano llevará a lograr la factorización de cualquier entero n a partir de un número menor a n
Muchas gracias por tu aportación.
Saludos
Publicar un comentario