def pollard_rho(n, x0, c):
x, y = x0, (x0 * x0 + c) % n
while (g := math.gcd(x - y, n)) == 1:
x, y = (x * x + c) % n, (y * y + c) % n
y = (y * y + c) % n
return gdef find_factor(n):
if is_prime(n):
return n
x0 = 2
for c in itertools.count(1):
g = pollard_rho(n, x0, c)
if g != n:
return gdef prime_factors(n):
"""returns a Counter of the prime factorization of n"""
if n <= 1:
return Counter()
f = find_factor(n)
return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)def brent_pollard(n,x0,c):
m, l, x, g, q = 128, 1, x0, 1, 1
while g == 1:
y = x
for _ in range(l - 1):
x = (x * x + c) % n
k = 0
while k < l and g == 1:
xs = x
for _ in range(min(m, l - k)):
x = (x * x + c) % n
q = q * abs(y - x) % n
g = math.gcd(q, n)
k += m
l += l
if g != n:
return g
g = 1
while g == 1:
xs = (xs * xs + 1) % n
g = math.gcd(xs - y, n)
return g