要实现的是如图所示的算法（数字都很大，n可能是100位的整数）。chatgpt写的这个python算法，非常快
我自己按照 miller算法的原本思路，直接写的python（如下），慢得一塌糊涂。我的代码，非常慢，好理解。直接进行大整数的幂运算、整除取余数运算，确实非常慢。但是chatgpt实现的这个mod_exp(base, exp, mod)，我看不懂啊。大佬能提示一下吗？在miller_rabin(n,aa, k=1)函数里，有两个地方，调用了mod_exp函数。大佬能解释一下这个 mod_exp 到底是干嘛的吗？谢谢

def miller_rabin_zdl(n, k=1):
    if n <= 1 or n == 4:
        return False  # 0, 1 和 4 不是素数
    if n <= 3:
        return True  # 2 和 3 是素数

    # 找到 d，使得 n-1 = 2^s * d
    s = 0
    d = n - 1
    while d % 2 == 0:
        d //= 2
        s += 1
    b=2
    if (b**d -1)%n==0:
        return True
    for r in range(s):
        if (b**(2**r * d)+1)%n==0:
            return  True
    return False
if __name__ == "__main__":
    if miller_rabin_zdl(i):
        print(i,"是素数")

--
FROM 120.242.240.*

【 在 feng321 的大作中提到: 】
: [upload=1][/upload][upload=2][/upload][upload=3][/upload]
: 要实现的是如图所示的算法（数字都很大，n可能是100位的整数）。chatgpt写的这个python算法，非常快
: 我自己按照 miller算法的原本思路，直接写的python（如下），慢得一塌糊涂。我的代码，非常慢，好理解。直接进行大整数的幂运算、整除取余数运算，确实非常慢。但是chatgpt实现的这个mod_exp(base, exp, mod)，我看不懂啊。大佬能提示一下吗？在miller_rabin(n,aa, k=1)函数里，有两个地方，调用了mod_exp函数。大佬能解释一下这个 mod_exp 到底是干嘛的吗？谢谢
: ...................
检查x是不是素数，
米勒-素数检查是求 power(a, x-1)，
米勒-拉宾素性检验是求 power(a, power(2,r)*d)，
如果对应到这个mod_exp(base, exp, mod) 那base相当于是a的d次方， exp是r， mode是x
--
FROM 115.171.154.*