find all multiplicands and multipliers for a number

[Paul Rubin]

Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
> Um, "simple sieve"? You're using Miller-Rabin to check for candidate
> prime factors. I don't think that counts as a simple sieve :-)

How does Miller-Rabin help?  It has to cost more than trial division.

Meanwhile, trial division up to 100000 is almost instantaneous and gives
the factorization

  [3, 3, 1777, 3331, 17539, 2778562183799360736577L]

where the last factor is composite.

    def pollard(n):
        def g(x): return (x*x+1) % n
        x = y = 2
        while True:
            x,y = g(x), g(g(y))
            d = gcd(abs(x-y), n)
            if d != 1:
                return d

   print pollard(2778562183799360736577L)

finds the factor 25781083 almost instantly.  

Verifying that 25781083 and the remaining factor is prime, and patching
all the code together to factorize in one operation, is left as an
exercise ;-).

Note that the Pollard routine is not guaranteed to find a nontrivial
factor.  If it fails, try a starting value other than 2.  This is also
left as an exercise.