一、欧几里得算法

def exgcd(a, b):
    x_symbol = 1
    y_symbol = 1
    if a < 0:
        a = -a
        x_symbol = -1
    if b < 0:
        b = -b
        y_symbol = -1
    # 均按正数处理

    if b == 0:
        return 1, 0, a
    else:
        x, y, g = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)

        # 最小正整数x
        while x <= 0:
            x += b // g
            y -= a // g

        return x * x_symbol, y * y_symbol, g

二、快速幂取模

def fast_power(a, b, c):
    # 二进制表示b
    b = bin(b)[1:]

    t = 1
    for i in b:
        if i == "1":  # 从左向右读b，读到“1”将t平方乘a模c，读到“0”平方取模
            t = t * t % c * a % c
        else:
            t = t * t % c
    return t

三、中国剩余定理

def get_inv(a, b):
    a_symbol = 1
    b_symbol = 1
    if a < 0:
        a_symbol = -1
    if b < 0:
        b_symbol = -1
    a0 = [a * a_symbol, 1, 0]
    b0 = [b * b_symbol, 0, 1]
    if a0[0] < b0[0]:
        a0, b0 = b0, a0
    while b0[0] > 0:
        k = a0[0] // b0[0]
        for i in range(0, 3):
            a0[i] = a0[i] - k * b0[i]
        a0, b0 = b0, a0
    answer = a0[1]
    while answer < 0:
        answer += b
    return answer * a_symbol * b_symbol
# 这是扩展欧几里得求逆元的函数

四、Miller-Rabin素性监测算法

五、厄拉多塞筛

def Eeatosthese(n):
    if n < 3:
        return [1, 1]
    else:
        numbers = [1] * n
        for i in range(1, int(pow(n, 0.5)) + 1):
            if numbers[i] == 1:
                for j in range(2, n // (i + 1) + 1):
                    numbers[(i + 1) * j - 1] = 0
        return numbers