def factorize(N, e, d): from math import gcd import gmpy2 k = d*e - 1 t = k while t % 2 == 0: t //= 2 g = 3 while True: x = pow(g, t, N) if x > 1: y = gcd(x - 1, N) if y > 1: return y, N//y g = gmpy2.next_prime(g)
def factorize(N, e, d): from math import gcd import gmpy2 k = d*e - 1 t = k while t % 2 == 0: t //= 2 g = 3 while True: x = pow(g, t, N) if x > 1: y = gcd(x - 1, N) if y > 1: return y, N//y g = gmpy2.next_prime(g)