python代码输入两个公钥N和e利用素性测试算法和优化后的大数质因子分解算法实现RSA公钥解密算法

以下是实现RSA公钥解密算法的Python代码，需要用到pycryptodome库中的模块：

from Crypto.Util import number

# 素性测试算法
def is_prime(n, k=128):
    """
    Miller-Rabin素性测试算法
    """
    if n <= 3:
        return n == 2 or n == 3
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    for i in range(k):
        a = number.getRandomRange(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for r in range(1, s):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# 优化后的大数质因子分解算法
def factorize(n):
    """
    Pollard-Rho质因数分解算法
    """
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def rho(n):
        if n % 2 == 0:
            return 2
        x, y = number.getRandomRange(0, n - 1), 1
        c = number.getRandomRange(0, n - 1)
        k = 2
        while True:
            x = (pow(x, 2, n) + c) % n
            d = gcd(abs(x - y), n)
            if d != 1 and d != n:
                return d
            k -= 1
            if k == 0:
                y = x
                k = 2
            if x == y:
                c = number.getRandomRange(0, n - 1)
                y = 1

    if n <= 3:
        return [n]
    x, y = n, n
    while y == n:
        x = rho(x)
        y = rho(rho(y))
    p = gcd(x - y, n)
    if p == n:
        return factorize(n)
    return factorize(p) + factorize(n // p)

# RSA公钥解密算法
def rsa_decrypt(c, N, e):
    """
    RSA公钥解密算法
    """
    # 求出p和q
    factors = factorize(N)
    p, q = factors[0], factors[1]
    # 计算d
    phi_N = (p - 1) * (q - 1)
    d = number.inverse(e, phi_N)
    # 解密
    m = pow(c, d, N)
    return m

# 测试
if __name__ == '__main__':
    N = 196520507
    e = 65537
    c = 177252946
    m = rsa_decrypt(c, N, e)
    print(m)

其中，is_prime()函数是实现Miller-Rabin素性测试算法，用于检验一个数是否为素数；factorize()函数是实现Pollard-Rho质因数分解算法，用于对大数进行质因数分解；rsa_decrypt()函数是实现RSA公钥解密算法，用于解密RSA加密后的密文。

测试部分给出了一个示例，使用上述代码解密RSA加密后的密文。