'''Number Theory''' import random def isPrime(m): if m in [2, 3, 5, 7, 11, 13, 17, 19]: return True if m%2 == 0 or m < 20: return False d = 3 while d*d <= m: if m%d == 0: return False d += 2 return True def factorize(m): factors = [] if m == 0: return factors if m < 0: factors.append((-1, 1)) m = (-m) d = 2 while m >= d: if m%d == 0: e = 1 m //= d while m%d == 0: e += 1 m //= d factors.append((d, e)) d += 1 if m > 1: factors.append((m, 1)) return factors def powmod(x, n, m): assert(n >= 0) p = 1; y = x%m; k = n # Invariant: p * y^k == x^n (mod m) while k != 0: if k%2 == 0: k //= 2 y = (y*y)%m else: k -= 1 p = (p*y)%m return p def gcd(m, n): assert m != 0 or n != 0 (a, b) = (m, n) while b != 0: (a, b) = (b, a%b) if a > 0: return a else: return (-a) def extEucl(m, n): assert m != 0 or n != 0 (a, b) = (m, n) u1 = 1; v1 = 0 u2 = 0; v2 = 1 while b != 0: q = a//b; r = a%b (a, b) = (b, r) (u1, u2) = (u2, u1 - q*u2) (v1, v2) = (v2, v1 - q*v2) if a > 0: return (a, u1, v1) else: return (-a, -u1, -v1) def invmod(n, m): assert m != 0 (d, u, v) = extEucl(m, n) if d != 1: raise ZeroDivisionError( "Element is not invertible modulo m" ) return v%m def chineseReminderAlg(r1, r2, m1, m2): v = invmod(m1, m2) s = (v*(r2 - r1))%m2 return r1 + s*m1 def squareSequence(b, m): assert m%2 != 0 t = m - 1 s = 0 while t%2 == 0: t //= 2 s += 1 assert t*(2**s) == m - 1 res = [] x = powmod(b, t, m) res.append(x) for i in range(s): x = x*x%m res.append(x) return res smallPrimes = [2, 3, 5, 7, 11, 13] wheelLength = 1 for p in smallPrimes: wheelLength *= p inversesModWheelLength = [ d for d in range(1, wheelLength) if gcd(d, wheelLength) == 1 ] def spokedWheel(m): ''' Find a factor of integer number m using the Spoked Wheel algorithm. Return 1 if m is prime. ''' for d in smallPrimes: if m%d == 0: return d k = 0 while True: for x in inversesModWheelLength: if k == 0 and x == 1: continue d = k*wheelLength + x if d*d > m: return 1 if m%d == 0: return d k += 1