import sysdef gcd(p, q): if q == 0: return p return gcd(q, p % q)p = int(sys.argv[1])q = int(sys.argv[2]) print(gcd(p, q))

这段代码实现了求两个数的最大公约数，其中 p 和 q 是从命令行参数中读入的。算法使用了辗转相除法，即不断用较小的数去除较大的数，直到两个数相等或者其中一个数变成0。如果其中一个数变成0，则另一个数即为最大公约数。如果两个数不相等，则用较小的数去减较大的数，再用这个差和较小的数继续进行辗转相除，直到两个数相等为止。最后的相等点即为最大公约数。

相关问题

python基于RSA算法的非对称数字签名，要求，p，q不需要大素数，普通素数即可，但p，q，e要求为可输入数字，认证信息为任意可输入数字

以下是基于RSA算法的非对称数字签名的Python代码示例：

import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return (gcd, y - (b // a) * x, x)

def mod_inv(a, m):
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def generate_key(p, q, e):
    if (not is_prime(p)) or (not is_prime(q)):
        raise Exception('p or q is not prime')
    n = p * q
    phi = (p - 1) * (q - 1)
    if gcd(phi, e) != 1:
        raise Exception('e is not coprime to phi')
    d = mod_inv(e, phi)
    return ((n, e), (n, d))

def sign(message, private_key):
    n, d = private_key
    m = int(message)
    return pow(m, d, n)

def verify(message, signature, public_key):
    n, e = public_key
    m = int(message)
    s = pow(signature, e, n)
    return s == m

# Example usage
p = 17
q = 19
e = 7
public_key, private_key = generate_key(p, q, e)
print('Public key:', public_key)
print('Private key:', private_key)
message = input('Enter message to sign: ')
signature = sign(message, private_key)
print('Signature:', signature)
valid = verify(message, signature, public_key)
if valid:
    print('Signature is valid')
else:
    print('Signature is not valid')

在代码中，`generate_key()`函数用于生成密钥对，`sign()`函数用于对消息进行签名，`verify()`函数用于验证签名。

需要注意的是，由于本算法不要求p，q为大素数，因此安全性较低，实际使用中应当使用大素数。同时，在签名时需要将待签名的消息转换为整数类型。