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 -- http://mail.python.org/mailman/listinfo/python-list