import random from math import gcd def isPrime(m): '''Check whether m is a prime number''' if m in (2, 3, 5, 7): return True if m <= 10 or m%2 == 0: return False d = 3 while d*d <= m: if m%d == 0: return False d += 2 return True def factor(m): '''Factorize an integer m. Return a list of pairs (prime factor, its exponent). Example: for m = 60 the result is [(2, 2), (3, 1), (5, 1)]''' if type(m) != int: raise ValueError("non-integer argument of factor(m)") if m == 0: return [(0, 1)] factors = [] if m < 0: m //= (-1) factors.append((-1, 1)) assert m > 0 d = 2 while d*d <= m: if m%d == 0: e = 0 while m%d == 0: m //= d e += 1 factors.append((d, e)) d += 1 if m > 1: factors.append((m, 1)) return factors def f(x, m): return (x*x + 1)%m def pollardRhoFactor(m, maxSteps = 10000000): '''Find a nontrivial divisor of m. Return 1 if this is not possible''' if m > 4: x = random.randrange(2, m-1) # Initial point else: x = 2 y = f(x, m) d = gcd(x - y, m) step = 0 while d == 1 and step <= maxSteps: x = f(x, m) y = f(y, m) y = f(y, m) d = gcd(x - y, m) step += 1 if d == m: d = 1 return d