Métodos de factorización de números naturales

[Gaussito]

En otro hilo prometí aportar mis propios métodos de factorización (aunque como siempre pasa en Matemáticas, habrá mucha gente que ya los ha trabajado, pero digo que son propios puesto que son fruto única y exclusivamente de mis razonamientos), por tanto inicio este nuevo tema para todo aquél que quiera presentar un método de factorización, pueda exponerlo acá y así tener un referente organizado de métodos, los cuales puedan ser citados en futuras conversaciones, o sirvan de referencia para futuros estudios con respeto a este tema.

Advierto que los métodos que expondré son en extremo ineficientes cuando se tratan de números grandes, y no pretendo aportar avances en este sentido, sólo quiero reflejar que el método clásico para la factorización no es el único camino, y a mi criterio, creo necesario estudiar nuevas formas de factorización, puesto que si seguimos iterando, jamás podremos factorizar números suficientemente grandes (mas de 1 millón de cifras).

Sugiero seguir una numeración, para trabajar de forma organizada, además, separar los métodos en comentarios exclusivos, para hacer más fácil consultas futuras. Sin más preámbulo comienzo a explicarlos:

[Gaussito]

Método 1: Factorización Geométrica

Quisiera comenzar por éste, que aunque es el mas ineficiente de todos, a mí me parece el más hermoso, porque relaciona la factorización con la geometría. Se basa en el hecho de que la altura en un triángulo rectángulo, viene dada por: [texx]h^2=p.q[/texx], donde [texx]p+q[/texx] es igual a la hipotenusa. Además, esa misma hipotenusa, es el diámetro de un círculo que pasa por los vértices del triángulo.

Entonces, tomando en cuenta esos elementos, construyo una figura geométrica donde se muestra esa relación. Explico mejor con un ejemplo: supongamos que me dan a factorizar el número 15, entonces digo que [texx](\sqrt[ ]{15})^2=p.q[/texx], ubico las raíces de 15 a un lado y al otro sobre el eje x (una negativa y otra positiva), luego ubico p en la coordenada (0 , 1), entonces como tengo 3 puntos, le puedo decir a un programa que trace una circunferencia por dichos puntos. Lo hermoso de esto, es que la circunferencia cortará por debajo al eje y, a una distancia de -q del origen. Después voy moviendo de uno en uno el punto p.... (0 , 2); (0 , 3) y así sucesivamente, generando por debajo los valores de q.

La idea de esto es moverse de uno en uno hasta obtener que q sea un entero.

Y por supuesto, por ser un método geométrico lo creé en Geogebra (advierto que soy nuevo con ese software). Espero lo revisen y sepan apreciar la bonita relación. (En el software coloqué el número 527 = 17 . 31, pero ustedes pueden introducir cualquier valor, que sugiero sea pequeño).

Finalmente, con métodos como este se puede apreciar que con compás y regla también podríamos factorizar.

[Gaussito]

Método 2: Factorizando en un sistema de numeración unitario

Antes que nada quiero decir que este método no es 100% de mi creación, lo leí en otro hilo donde usaban la programación para factorizar, pero usaban en vez de números cadenas de textos (cuando lo vuelva a conseguir editaré para introducir la cita), en mi caso creo que lo mejoré un poco. Además, para aplicarlo eficientemente, recomendaría aprender lenguaje de máquina, es decir, no programar en ningún lenguaje de alto nivel, sino hablarle person to person a la computadora, para que haga única y exclusivamente lo que nosotros le pedimos y no pierda recursos en cálculos innecesarios.

La idea principal es muy sencilla, imaginemos que me dan a factorizar el número 35, entonces escribimos 35 palitos en una hoja (por eso digo que es un sistema de numeración de base 1), Así:

11111111111111111111111111111111111

Luego comenzaremos a iterar, para verificar si es por ejemplo divisible entre 2, sustituyendo por un cero, es decir:

10101010101010101010101010101010101 , como al final me sobró un 1, no es divisible entre 2. Veamos si lo es entre 3.

11011011011011011011011011011011011 , me sobraron 2 unos, por tanto no es divisible entre 3. Probemos con 4.

11101110111011101110111011101110111 , me sobraron 3 unos, tampoco es divisible entre 4. Probemos con 5.

11110111101111011110111101111011110 , Eureka!, como el último número es un cero, entonces si es divisible entre 5.

Ahora bien, el proceso parece igual al clásico, sin embargo intuyo que computacionalmente hablando, requiere de menos cálculos para una computadora programada en lenguaje máquina. Por ejemplo, tomemos un disco duro de un terabyte, cuya cantidad de bits es: 8.796.093.022.208, supongamos que queremos factorizar ese número.

Aplicando este método, tendríamos primero que colocar todos los bits en 1, cosa que creo será fácil, luego comenzamos con el proceso de iteración. Claro que como sabemos, sería una pérdida de tiempo iterar de uno en uno, por tanto usando análisis estructurales de la aparición de primos, iteraríamos como mínimo con números de la forma 6k+1 o 6k-1.

Sin embargo creo que este método es en general ineficiente, primero habría que ver si tengo razón en que computacionalmente es más rápido que con lenguajes de alto nivel, y aún teniendo razón, el método requeriría de mucho espacio de disco duro para factorizar números grandes, que como vimos en el ejemplo de un disco de un tera, solamente podríamos factorizar números menores que 8.796.093.022.208.

[Gaussito]

Método 3: Ampliación del número a factorizar

De este método ya había hablado anteriormente, y se basa en puras especulaciones. Yo creo que existen números que por su conformación de cifras, son más fáciles de factorizar que otros, por ejemplo números cuyas cifras sólo sean unos y ceros, es decir, 1110 ó 11111111100.

De ser esto cierto, y cómo sabemos (mentira, en realidad yo no lo sé, jejejejejeje), que todo número natural, se puede multiplicar por otro para llevarlo a la forma de unos y ceros, entonces en el proceso de factorización simplemente ampliamos el número que nos dan, los llevamos a la forma fácil de factorizar, y luego de allí quedará factorizado fácilmente.

Por ejemplo, tratemos de factorizar el 35:

Lo multiplicamos por 31.746 * 35 = 1.111.110

Luego, supongo que tengo un algoritmo que factoriza directamente el número 1.111.110, quedará directamente factorizado el número 35.

Muchos al leer esto lo verán como un empeoramiento del problema, porque si era difícil factorizar el 35, muchísimo peor será factorizar 1.111.110. Pero a pesar de que estoy al tanto de un posible agravamiento del problema, tengo ciertas esperanzas de que tales números fáciles existan, y al menos al proponer este método, animaría a otros a explorar qué números pueden ser fáciles de factorizar. Con esta idea de números de la forma 111111....11110000, estaría reduciendo el estudio de la factorización de todos los números naturales, a solo estudiar números con la forma de unos y cero, por esto creo que en general la idea es buena.

Además, alguien más adelante podría desarrollar un algoritmo para factorizar números de la forma 121212121212...., o cualquier otro patrón de números, entonces este método de la ampliación sería relevante.

[Gaussito]

Método 4: Estudio del período

Hace algunas semanas inicié un hilo donde se estudiaron (en realidad El_manco e Ivorra lo dijeron todo, yo solo aprendía y llevaba a la práctica sus recomendaciones) algunas propiedades del período que se genera al dividir dos números naturales (http://rinconmatematico.com/foros/index.php?topic=88140.0), allí se observaba que el período generado por la división de dos coprimos siempre es de la misma cantidad de cifras, sin embargo, cuando los números a dividir tienen factores primos comunes, el número de cifras del período se reduce al nuevo denominador que queda luego de la correspondiente simplificación, colocaré un ejemplo para observar lo que digo:

Supongamos que nos piden factorizar el 77, entonces estudiaremos sus periodos con fracciones del tipo [texx]\displaystyle\frac{n}{77}[/texx], comenzamos con n=1.

[texx]\displaystyle\frac{1}{77} = 0.012987 012987 012987 012987....[/texx], vemos que tiene un período de 6 cifras. Ahora n=2.

[texx]\displaystyle\frac{2*1}{77} = 2*0.012987.... = 0.025974...[/texx], igual tiene 6 cifras el período, porque como dijimos antes, los factores a dividir son coprimos. Así seguimos el proceso, pero veamos lo que pasa cuando n = 7.

[texx]\displaystyle\frac{7*1}{77} = 7*0.012987.... = 0.090909...[/texx], como vemos el período ahora tiene sólo 2 cifras, esto se debe a que 7 es divisor de 77, y al simplificar me queda la fracción [texx]\displaystyle\frac{1}{11}[/texx], y al ser coprimos, toma el período del denominador y como sabemos, todos número dividido entre 11, da períodos de 2 cifras. Sin embargo, cuando continuamos la iteración, veremos que cuando n=8, vuelven a aparecer las 6 cifras en el período. Es decir, que cuando n es divisor del número a factorizar, cambia la cantidad de cifras del período (esto tienes sus excepciones, pero con pequeños ajustes a lo que digo, fácilmente se solucionan los casos particulares).

En fin, mi idea de factorización es la siguiente, calculamos el período dividir 1 entre el número a factorizar (en mi ejemplo 0.012987....), luego al ir multiplicando dicho período por 2, 3, 4, ....., n, aparecerá un número cuya cantidad de cifras en el período cambie, y al notar ese cambio, es porque dicho número es un divisor del número a factorizar.

Esto les sonará a la bendita iteración que a mi parecer no favorece en nada a un método de factorización directa, pero creo que en este caso dicha iteración no será necesaria, si descubrimos una forma alternativa de descubrir cuando la cantidad de cifras del período cambie, tomando en cuenta que de lo que se trata es de sumar n veces el número fijo 0.012987...., hasta que dentro de esas 6 cifras se de otro patrón de período.

[Gaussito]

Método 5: Factorización directa

Como siempre acostumbro, dejo lo mejor para el final, jejejejejeje. Este a mi parecer es el método en el que pongo todas mis esperanzas, con decirles que la pizarra de mi casa tiene más de 2 semanas que no la borro con los detalles de este método, y cada vez que puedo me siento un rato a pensar como salir del atolladero en que me encuentro.

Este método es simple, consiste en que si me dan a factorizar por ejemplo el número 1517, simplemente digo que es un producto de dos números primos de la forma ab * cd, y comienzo mi análisis de cifras. Evidentemente como ab y cd, son primos, sus últimos dígitos serán 1, 3, 7 o 9 (esto no es tan evidente, pero a buenos entendedores pocas palabras). Entonces, cómo el producto ab * cd = 1517, quiere decir que la unidad del producto de b * d = 7, ahora de las cuatro posibles cifras que pueden tener b y d, los únicos que dan como resultado un número terminado en 7 son (1 y 7) ó (9 y 3), entonces puedo suponer que b = 1 y d = 7.

Por tanto, los números ab y cd, ahora serán a1 y c7. Sin embargo, la raíz cuadrada de 1517 es 38,94 , lo que quiere decir que uno de los números tiene sus primeras cifras de 1 o 2 o 3. Entonces supongo que c = 1, es decir que cd = 17, divido 1517 entre 17 y veo que no es divisible, sigo con c = 2, y pruebo a ver si 27 divide a 1517, pero tampoco lo divide, ahora pruebo con c = 3, y divido 1517 entre 37 y felizmente me da 41, por tanto al factorizar el número nos queda 1517 = 37 * 41.

Parece un método rebuscado, donde hay que ir probando al tanteo hasta dar con el número buscado, además se habrán dado cuenta que me faltaron muchas cosas por probar, es decir, pude comenzar diciendo que los números dados terminaban en 9 y 3, y así nunca fuese encontrado los factores perdiendo mi tiempo con todas las pruebas. Peor aún, cuando los números son muy grandes, las cosas se complican mucho más, además también supuse que los números eran de 2 cifras cada uno, pero esto no es necesariamente cierto.

En fin, quien analice el procedimiento que acabo de explicar, lo verá como tosco e ineficiente, pero en realidad no es así. Cuando analizamos sesudamente y comenzamos a plantear ecuaciones, nos encontraremos con soluciones directas, donde no sería necesario probar con ningunos números fallidos, sino que podríamos dar directamente con los factores del número compuesto.

El problema en el que estoy atascado es el siguiente, me encuentro con ecuaciones del tipo, buscar dos números (de una cifra, siempre serán de una cifra y eso es una de las grandes ventajas de este método) cuya decena al multiplicar sea 7. Entonces analíticamente no encuentro como resolver este tipo de ecuaciones, aun sabiendo que al mirar la tabla de multiplicar, el único resultado posible sea 9*8=72, entonces en números grandes se generan sistemas de ecuaciones de este tipo:

d(a.b)+u(b.c)+d(c.e)+3 = #5 ; donde u(a.b) significa unidad de a por b y d(a.b) significa decena de a por b.

Que a pesar de que tienen varias soluciones posibles, al formar el conjunto de ecuaciones de este tipo, la solución es única (esto también tiene sus excepciones). Por último, creo que lo necesario para salir del atollamiento en que me encuentro con este método, es disponer de un álgebra de unidades y decenas, al igual que se dispone de un álgebra de módulos, con una teoría como la que se aplica con los módulos, creo que se podría avanzar bastante en este método.

Finalmente, no crean que me he quedado viendo mi pizarra sin lograr avances, ya he vislumbrado algunas ideas, que si llegan a buen término, las expondré en comentarios futuros (o quizás no, si doy con algo importante, llamo a los dueños de google y les vendo mis tonerías, jejejejejejejejeje).

Saludos.

PD. Invito a Victor Luís y Feriva, que expongan aquí sus métodos de factorización, y a cualquier otro que tenga uno, además revisen mis métodos y critíquenlos a mas no poder, quien quita y salga algo bueno de estas conversaciones.

[feriva]

Método 2: Factorizando en un sistema de numeración unitario

Hola, Gaussito. Yo inventé una cosa parecida pero el objetivo era obtener los divisores de los números mediante una tabla.

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0
0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0
0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0
0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0
...
etc., hasta 25 filas.

Aquí lo que tenemos es el número 25.

En columna, el primer 1 de la primera fila se corresponde con el número 1, el segundo 1 de la primera fila, con el número 2, etc.

La segunda fila empieza con un cero y alterna con unos, de manera que va señalando los pares respecto a los unos de arriba, en columna. La tercera marca los los “lugares” de los múltiplos de 3, etc.

Si te fijas en la cuarta columna y cuentas la cantidad de unos (de la columna) encontrarás que es la cantidad de divisores de cuatro, hay tres unos, que se corresponde con los divisores 1,2 y4; en la sexta encontramos cuatro unos, que se corresponde también con los divisores de 6, esto es, 1,2,3,6,  si seguimos añadiendo las filas que faltan, hasta 25, podrás ver que la cantidad de unos coincide también con la de los divisores de los números sucesivos. Y donde sólo haya dos unos tendremos un primo, tendremos los divisores 1 y el primo.

Hice un programa en Python para calcular los divisores mediante este sistema (no es eficiente, fue por la curiosidad, y acababa de empezar a conocer Python y por otra parte soy bastante chapucero programando, así que no te rías de mi poca habilidad porque si sabes código máquina o ensamblador... quiere decir que sabes mucho de programación). Se lo puse por ahí a Víctor Luis el año pasado, o hace dos años, junto a la explicación de cuál era la idea para hallar los divisores mediante este método rupestre; el programa es éste:

Spoiler (click para mostrar u ocultar)

import os

d=[]
suma=0
k=0
x=400
n=1



for i in range (1,x):
   c=(([0]*i)+[1])*i
   d.append(c)



def vectores():

   for j in range(1,x):
   
      d[k]=d[k]+f
   
      if len(d[k]) > x:
         break
         
for k in range(0,x-1):

   f=d[k]
   vectores()
   
while(n>0):   
   n=int(raw_input("\n\n\n\n\n\n\n\n\n        ingresa un numero del 1 al 400\n\
   (para salir del bucle pulsa 0 y Enter): "))
   
   os.system("clear")
   
   if(n==0):
      break
   n=n-1
   for m in range(0,x-1):
      suma+=(d[m][n])
   if (suma==1):
      print "\n\n                             %d es primo" %(n+1)
      suma=0
   else:
      print "\n\n                             %d tiene %d divisores" %(n+1,suma+1)
      suma=0   
      

*Como esto no es un método en sí para factorizar aunque quizá sí podría dar una idea de la cual partir, lo pongo como un simple comentario a tu método 2 y no aparte; pero si quieres que lo ponga de otra forma o que haga algo en cuanto a la numeración o eso que explicas, me lo dices.

Saludos. 

[Gaussito]

Hola, Gaussito. Yo inventé una cosa parecida pero el objetivo era obtener los divisores de los números mediante una tabla...

Tristemente en Matemáticas parece que ya todo está hecho, pero igualmente es satisfactorio redescubrir las cosas, y sí tu razonamiento es prácticamente el mismo que el mío.

Hice un programa en Python para calcular los divisores mediante este sistema (no es eficiente, fue por la curiosidad, y acababa de empezar a conocer Python y por otra parte soy bastante chapucero programando, así que no te rías de mi poca habilidad porque si sabes código máquina o ensamblador... quiere decir que sabes mucho de programación). Se lo puse por ahí a Víctor Luis el año pasado, o hace dos años, junto a la explicación de cuál era la idea para hallar los divisores mediante este método rupestre; el programa es éste:

Yo ni siquiera sé programar en Python, pero con algo de esfuerzo entiendo la lógica de programación de este lenguaje (debido a que programo en otros lenguajes), además tampoco sé lenguaje ensamblador, pero si he leído cual es el procedimiento para que un lenguaje de alto nivel como Python, haga una operación matemática, y me parece una pérdida de recursos del sistema cuando lo que queremos de la computadora es que haga algo tan sencillo como intercalar ceros cada 2 unos. Por eso hablé de que este método sería más eficiente si lo hacemos en lenguaje ensamblador, e inclusive creo que cuando se trata de tareas específicas como factorizar números, siempre será más eficiente hacerlo con un lenguaje ensamblador y así hacer que la computadora haga solamente lo que queremos que haga, sin perder recursos en otras operaciones.

Saludos.

[feriva]

Tristemente en Matemáticas parece que ya todo está hecho

Supongo que queda por hacer, sí que es verdad que todos los caminos llevan a Roma, como le he dicho a Víctor Luis algunas veces. Es normal que todos pensemos cosas muy parecidas o iguales con distintos enfoques, porque cuando se intenta que rija la lógica las puertas que se van a abriendo para llegar a un sitio son las que son aunque pueda haber variantes, y los números también son los que son.

pero si he leído cual es el procedimiento para que un lenguaje de alto nivel como Python, haga una operación matemática, y me parece una pérdida de recursos del sistema cuando lo que queremos de la computadora es que haga algo tan sencillo como intercalar ceros cada 2 unos

Sí, sin duda, eso es verdad, pero, con la compilación, los programas hechos en lenguajes de alto nivel quedan prácticamente como si estuvieran hechos en código máquina;  aunque no sé muy bien hasta qué punto, no soy experto ni mucho menos. Yo aprendí un poquito, casi nada, de ensamblador, cuando aparecieron los primeros ordenadores personales, con un Spectrum; el problema era que tardabas mucho más en programar, para programar una tontería te quedaba un código fuente muy largo y te llevaba mucho tiempo. Hoy en día no sé si será igual, aunque supongo que seguirá siendo más largo. En Youtube hay varios cursos de programación de ensamblador, no lo he mirado, sólo lo vi un día muy por encima; te pongo uno de ellos, por si te interesa.



https://www.youtube.com/watch?v=F98S6CN6KM0

Saludos.

[sqrmatrix]

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órico

Partimos 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áctico

Así, 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:

Código:

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 variante

Hace 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.

[Gaussito]

Sqrmatrix gracias por tus aportes...

Aunque me gustaría aclarar que el método clásico de Fermat es más sencillo, es decir, dado un m = p.q, decimos que [texx]p = a+b[/texx] y [texx]q=a-b[/texx], con a y b naturales, luego al sustituir, nos queda:

[texx]m=p.q=(a+b).(a-b)=a^2-b^2[/texx], de aquí que:

[texx]b^2=a^2-m[/texx]

Es decir, comenzamos desde [texx]\sqrt[ ]{m}[/texx] a iterar sobre a (sabiendo que [texx]a>\sqrt[ ]{m}[/texx] por el teorema de Pitágoras), hasta que [texx]a^2-m[/texx] sea un cuadrado perfecto.

Como vemos, esto cambia el enfoque clásico de la factorización, puesto que en vez de empezar a probar si los primos dividen a m, probaremos si la resta señalada es un cuadrado. Sin embargo, hay que señalar que este método es muy eficiente cuando los primos están cerca de la raíz cuadrada de m, pero en general es tan lento como el método clásico.

No obstante, el método de Fermat es la base de los mejores algoritmos de factorización, por ello creo que debe ser estudiado y combinado con otros métodos para factorizar los números grandes en el menor tiempo posible.

Saludos.

[sqrmatrix]

Saludos, Gaussito.

Aunque me gustaría aclarar que el método clásico de Fermat es más sencillo, es decir, dado un m = p.q, decimos que [texx]p = a+b[/texx] y [texx]q=a-b[/texx], con a y b naturales, luego al sustituir, nos queda:

Sí, es cierto que el método de Fermat es más sencillo que el que propongo. Sin embargo, el que propongo es más rápido cuando se cumplen ciertas condiciones. Te voy a poner el ejemplo que me dio la idea del algoritmo que he expuesto, para que se pueda entender esta ventaja.

En un libro de criptografía, en el que explicaban el criptosistema RSA, explicaban unas condiciones mínimas que debían cumplir los primos elegidos para RSA (ahora mismo no recuerdo esas condiciones que decían). Después de explicarlas, dieron una receta simple para obtener estos primos. Esta receta consistía en lo siguiente: elegimos un primo aleatorio [texx]\displaystyle p[/texx] de [texx]\displaystyle n[/texx] bits. Calculamos [texx]\displaystyle q=2p+1[/texx]. Si [texx]\displaystyle q[/texx] es primo, ya tenemos los primos para construir la clave RSA, donde [texx]\displaystyle m=p\cdot q[/texx]. Si no, repetimos el procedimiento. El par de primos obtenido así cumplen las condiciones expuestas en el libro.

Si aplicásemos el método de Fermat para factorizar [texx]\displaystyle m[/texx], nos encontramos con que la diferencia entre los primos que lo constituyen es de [texx]\displaystyle q-p=(2p+1)-p=p+1[/texx], que es un número muy grande (si lo hemos elegido grande, claro).

Veamos qué ocurre con el método que he planteado. Aquí tenemos que [texx]\displaystyle q=2p+1[/texx], es decir, que [texx]\displaystyle a=2[/texx] y [texx]\displaystyle b=1[/texx], números pequeños. Como indiqué, si [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son pequeños, el método factoriza rápidamente el entero. Apliquemos el algoritmo:

El valor de [texx]\displaystyle k[/texx] normalmente será relativamente pequeño, ya que es poco probable que la relación [texx]\displaystyle q=a\cdot p\pm b[/texx] tenga un valor de [texx]\displaystyle a[/texx] grande. Esto supondría que [texx]\displaystyle p[/texx] es muy pequeño y [texx]\displaystyle q[/texx] muy grande, y se podría factorizar por búsqueda exhaustiva. Pongamos que hacemos [texx]\displaystyle k=1000[/texx].

Empezamos dándole a [texx]\displaystyle b[/texx] el valor [texx]\displaystyle 0[/texx]. Recorremos el valor de [texx]\displaystyle a[/texx] desde [texx]\displaystyle 1[/texx] hasta [texx]\displaystyle k=1000[/texx], intentando encontrar una factorización. No la encontraremos porque recordemos que los valores que toman para la expresión [texx]\displaystyle q=a\cdot p\pm b[/texx] son [texx]\displaystyle a=2[/texx] y [texx]\displaystyle b=1[/texx].

Ahora incrementamos [texx]\displaystyle b[/texx] en [texx]\displaystyle 1[/texx], de forma que ahora valdrá [texx]\displaystyle 1[/texx]. Repetimos el procedimiento de antes. Damos a [texx]\displaystyle a[/texx] el valor [texx]\displaystyle 1[/texx], y vemos que no encontramos una factorización. Pero al darle a [texx]\displaystyle a[/texx] el valor [texx]\displaystyle 2[/texx], la encontramos, pues ahora [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] toman los valores que cumplen la relación [texx]\displaystyle q=a\cdot p\pm b[/texx].

Como se puede ver, en este caso, el número de iteraciones ha sido de [texx]\displaystyle k=1000[/texx] más [texx]\displaystyle 2[/texx], muy inferior a las que necesitaríamos aplicando el método de Fermat si [texx]\displaystyle p[/texx] es muy grande.

Cuando en la relación [texx]\displaystyle q=a\cdot p\pm b[/texx], ocurre que [texx]\displaystyle a=1[/texx], entonces el método de Fermat es más rápido. En el método que propongo, si [texx]\displaystyle q=a\cdot p\pm b[/texx], el número de iteraciónes será de [texx]\displaystyle k\cdot b+b+1=(k+1)\cdot b+1[/texx].

Quizá se podría combinar el método de Fermat con el que propongo, de forma que el método de Fermat se emplearía en lugar del caso [texx]\displaystyle a=1[/texx], y el método que propongo para [texx]\displaystyle a=2 ... k[/texx]. De esta forma, si resulta que en la expresión [texx]\displaystyle q=a\cdot p\pm b[/texx], ocurre que [texx]\displaystyle a=1[/texx], encontraremos la factorización antes. Aunque se realizarán más intentos que si utilizáramos simplemente el método de Fermat (todos los de [texx]\displaystyle a=2 ... k[/texx]).

[Gaussito]

Buenas noches, después de mucho buscar y probar diferentes software, he encontrado una aplicación totalmente funcional que permite usar los más modernos algoritmos de factorización, adjunto el link:

https://sourceforge.net/projects/yafu/

La intención de compartir este software en este hilo, es que si alguien tiene algún método nuevo de factorización, lo comparemos con los algoritmos más modernos y así determinar si se ha hecho avances en este sentido.

Saludos.

PD. Aunque probé con muy buenos resultados el programa, cada quien que asuma su responsabilidad por descargar y ejecutar dicha aplicación.

[macerox]

Yo propongo este:
http://rinconmatematico.com/foros/index.php?topic=102971cuadrados.0
Se llama factorización de enteros por diferencia de números triangulares. Es muy similar al de Fermat solo que este funciona más rápido cuando un factor es cercano al doble del otro y el de Fermat cuando están muy cerca los dos factores. Saludos.

[Scolnik]

Recién vi este foro y quiero aclarar algo. Hace tiempo introduce la idea de target y creo que las discusiones que vi dejaron de lado un hecho fundamental: dado un entero impar siempre existen targets únicos, por ejemplo con c=3,4 (se demuestra)

Las dificultades no surgen entonces de saber si existen targets únicos. Con un doctorando hemos avanzado bastante en este tema que es muy difícil

Saludos cordiales