Hay veces que uno empieza a programar sin rumbo y acaba con algo medianamente útil, este es uno de esos casos. Resulta que en el tren se me ocurrió "diseñar" un algoritmo de factorización para números grandes ( muuuuy grandes :P ) que funcionara como los test de primalidad de Fermat y Rabin- Miller es decir, confiando en que /dev/random guíe al programa por la senda adecuada.

Pero como el que escribe sabe poco ( o menos ! ) de matemáticas y no había ganas de documentarse sobre los otros test, pues todo acabó con un algoritmo chorra sin ninguna base real, así que:
1.
2. Puede encontrar los factores... o no
3.
4. No siempre encuentra a la primera los factores primos, de hecho no
encuentra siempre los mismos factores, alguna vez unos otra vez otros
( eso sí, todos correctos ), se puede descomponer del todo aplicandolo
de forma recursiva hasta que sean lo suficientemente pequeños para
aplicar una factorización lineal.
5.
6. La posibilidad de encontrar o fallar depende del número de iteraciones,
con Python unas 10,000 ( suficiente para casi cualquier número ) se
hacen en 5 segundos
7.

El algoritmo es el siguiente:

2. Se guarda el número a factorizar como N
4. Se le aplica la raíz cuadrada a N, obteniendo L
6. Se obtiene X a partir de L, restándole 1 si es par
8. Se inicia un contador I a 0 y una lista vacía D
10. Se añade X a la lista D
12. Se asigna a Q,  N % X
14. Si Q es 0, X es un factor, fin.
16. Sinó, se le suma 1 a Q si es impar
18. Se le resta Q a X, módulo L
20. Se incrementa I
22. Si X es mayor que 1 y no está en D,  si I es menor que el número de
    iteraciones se salta a 5, en caso contrario no se encontraron factores,
    fin.
24. Se toma un número X aleatorio impar entre 3 y L
26. Si X está en D, volver a 12
28. Sinó, salta a 5
    29.

Aquí hay que hacer notar algo muy importante, el número de iteraciones debe ser mayor o igual que L-2, sinó puede quedarse atascado en el bucle 12 - 13.

Y esta es la implementación en python:

!/usr/bin/env python

-- encoding: utf-8 --

Dumb factoring algorithm

Written by kenkeiras kenkeiras@gmail.com

Released under the WTFPL license

from sys import argv, stderr,stdout

from math import sqrt, pow

import random

Parity check

def mkpar(n, f=1):

if (n & 1) == 0:

   n += f

return n

Factoring

def facto(maxchk, l, n, iospeed = None):

result = None

x = l # Starting point

if not(x & 1):

    x -= 1

for i in xrange(maxchk):

    if (iospeed != None) and not(i % iospeed):

        stdout.write("%s / %s: %s%%" % (i,maxchk, (i*100)/maxchk))

        stdout.flush()

        stdout.write("\r")



     # Algorithm itself

    q = n % x

    chkd.append(x)

    if ( q == 0 ):

        result = x

        print "\n"

        break



    p = mkpar(q)

    x = ((x - (p)) + l) % l



    if x in chkd or x < 2:

        x = random.randint(3, l)|1



    while x in chkd:

         x = random.randint(3, l)

return result

Stub

if name == "main":

if len(argv) < 2:

   print >>stderr, argv[0], "<number> [<iterations>]"

   exit(0)

# Iteration number

defcheck = 10000

if len(argv) > 2:

    defcheck = int(argv[2])

n = int(argv[1]) # Target

print len(bin(n))-2, "bits"

l = int(pow(n, .5))

maxchk = min(defcheck, l-2)

print maxchk,"iteraciones"

chkd = [] # Already checked

iospeed = 0xFF

r = facto(maxchk, l, n, iospeed)

if (r == None):

   print (" "*20)+"\rNo hubo suerte :("

else:

   print (" "*20)+"\rResultado: %s, %s" % (r, (n / r))

Por ejemplo, con 12345678901234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 1234567890 123456789

[caption id="attachment_331" align="alignnone" width="300" caption="Captura del factorizador"][/caption]

Sé que realmente no es un número tan grande (492 bits), pero se puede lanzar contra uno de 1024 bits y sigue funcionando.

[caption id="attachment_332" align="alignnone" width="300" caption="A por los 1024 bits"][/caption]

Y eso es todo, no es gran cosa pero... brilla ! :P