Brent's variation of a factorization algorithm

[n00m]

Maybe someone'll make use of it:


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def brent(n):
    c = 11
    y, r, q, m = 1, 1, 1, 137
    while 1:
        x = y
        for i in range(1, r + 1):
            y = (y * y + c) % n
        k = 0
        while 1:
            ys = y
            for i in range(1, min(m, r - k) + 1):
                y = (y * y + c) % n
                q = (q * abs(x - y)) % n
            g = gcd(q, n)
            k += m
            if k >=r or g > 1:
                break
        r *= 2
        if g > 1:
            break
    if g == n:
        while 1:
            ys = (ys * ys + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break
    return g


while 1:
    n = eval(raw_input())
    g = brent(n)
    print '==', g, '*', n / g



IDLE 1.2      ==== No Subprocess ====

1170999422783 * 10001
== 73 * 160426920921271
1170999422783 * 254885996264477
== 1170999422783 * 254885996264477
1170999422783 * 415841978209842084233328691123
== 1170999422783 * 415841978209842084233328691123
51539607551 * 80630964769
== 51539607551 * 80630964769
304250263527209 * 792606555396977
== 304250263527209 * 792606555396977