Programming Praxis

The factorization is 100011322432435545 = 3 * 3 * 5 * 911 * 1051 * 48179 * 48179, and the program fails because of the squared factor; Pollard Rho finds both factors at the same time, then enters an infinite loop because the remaining cofactor is 1. This is a known problem with Pollard Rho, and with many other factoring algorithms also. As I advised my correspondent, that is the nature and the fascination of factoring. One solution is to check for squares before applying Pollard Rho, but that can still fail, because Pollard Rho is a probabilistic algorithm, so clearly I need to rewrite my standard “simple” factoring program, which handles numbers up to 25 or 30 decimal digits without trauma, and sometimes much larger numbers:

def factors(n):
    from fractions import gcd
    # 2,3,5-wheel to cube root of n
    wheel = [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs = 0, 2, []
    while f*f*f <= n:
        while n % f == 0:
            fs.append(f); n /= f
        if n == 1: return fs
        if isPrime(n):
            fs.append(n)
            return fs
        f, w = f+wheel[w], w+1
        if w == 11: w = 3
    # n must be semi-prime, so use
    # william hart's fermat variant
    if isSquare(n):
        f = isqrt(n);
        fs.append(f); fs.append(f)
        return fs
    for i in xrange(1,n):
        s = isqrt(n*i)
        if s*s <= n*i: s += 1
        m = pow(s,2,n)
        if isSquare(m):
            t = isqrt(m); f = gcd(n, s-t)
            fs.append(f); fs.append(n/f)
            return sorted(fs)

This uses a 2,3,5-wheel to find factors less than the cube root of n, followed by William Hart’s one-line factoring algorithm; we’ve discussed both in previous exercises. Now my correspondent’s factorization succeeds:

>>> factors(100011322432435545)
[3, 3, 5, 911, 1051, 48179, 48179]
>>> factors(13290059)
[3119, 4261]

Let’s consider the factorization of 13290059. The cube root of 13290059 is 237, so the prime wheel tries divisors up to 233, finding no factors. The number is not a square, so the one-line factoring algorithm begins. When i reaches 165, ni is 2192859735, s is 46828, m = 1849 = 43² is a perfect square, and gcd(13290059, 46828 – 43) is 3119, which is a factor of 13290059; the cofactor is 4261.

You can run the program at https://ideone.com/hTmzjd.

Pages: 1 2