编写求最大公因子的函数；编写求模逆的扩展欧几里得算法函数；编写rabin-miller素性检测算法函数；编写生成大素数的算法函数；编写生成RSA公私钥对的函数；编写RSA加密和解密函数

首先，我会分别解释这几个数学和计算机科学中的关键概念：

1. **最大公约数（GCD）函数**：可以使用欧几里得算法（也称辗转相除法）来编写，它通过不断取余数并更新两个数直到余数为0，最后一个非零余数即为最大公约数。

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

2. **模逆（Modular Inverse）函数**：利用扩展欧几里得算法可以在给定模数的情况下找到两个整数的最大公约数以及它们的乘积的逆元。这个函数会返回a关于b的逆元（如果存在的话）。

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

    _, d, _ = extended_gcd(e, m)
    if d < 0:
        d += m
    return d

3. **Rabin-Miller素性检测**：这是一种概率性算法，用于快速判断一个数是否为质数。虽然不是绝对确定，但在实际应用中非常有效。

import random

def is_probably_prime(n, k=5):  # 验证k次
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True

    s = n - 1
    r = 0
    while s % 2 == 0:
        r += 1
        s //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

4. **生成大素数**：通常使用随机性和一定的策略，例如检查一定条件下的数，同时保证足够大且满足素数定义。

def generate_large_prime(bit_size=1024):
    candidate = 2 ** bit_size + 1
    while not is_probably_prime(candidate):
        candidate += 2
    return candidate

5. **RSA公钥/私钥生成**：这涉及到选择两个大素数p和q，计算n=p*q，然后选择e（小于φ(n)= (p-1)(q-1) 的互质数），d作为e的模逆。公开的是n和e，保密的是d。

def rsa_key_pair():
    p, q = generate_large_prime(), generate_large_prime()
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 65537  # 公钥常用值，与phi_n互质
    d = mod_inverse(e, phi_n)  # 私钥
    return (n, e), (n, d)

6. **RSA加密/解密函数**：对于消息m，加密是m^e mod n，解密是c^d mod n。

def rsa_encrypt(message, public_key):
    n, e = public_key
    encrypted = pow(int(message), e, n)
    return encrypted

def rsa_decrypt(ciphertext, private_key):
    n, d = private_key
    decrypted = pow(ciphertext, d, n)
    return decrypted