RSA_recover_p_q.py

from Crypto.Util.number import long_to_bytes, bytes_to_long, GCD
from random import randint

def recover_p_q(n, e, d):
    k = d*e - 1
    if k & 1:
        return -1
    t = 0
    r = k
    while (r & 1 == 0):
        r = r // 2
        t += 1
    for i in range(1, 101):
        g = randint(0, n-1)
        y = pow(g, r, n)
        if (y == 1) or (y == n-1):
            continue
        for j in range(1, t):
            x = pow(y, 2, n)
            if x == 1:
                p = GCD(y-1, n)
                q = n//p
                return p, q
            if x == n-1:
                continue
            y = x
        x = pow(y, 2, n)
        if x == 1:
            p = GCD(y-1, n)
            q = n//p
            return p, q
    return -1