# Brent's variation of a factorization algorithm

n00m n00m at narod.ru
Fri Nov 27 16:36:29 CET 2009

```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

```