大素数的费马素数检验优化（DHKE 应用）

Question

因此，对于DHKE，我需要生成一个大的素数g（在本例中为>500位），然后计算N = 2g + 1，然后测试N是否是素数。重复该过程，直到找到这样的N。

为了实现这一点，我生成一个随机数g，在其上运行费马测试，然后在N上运行费马测试。但是，我注意到运行时间非常慢（有时程序需要几分钟）

以下是我在任意数字上实现的费马检验：

def fermatTest(p):

    for i in range(5):   # probability of getting a fool: 1/32

        a = secrets.randbelow(p)      

        if gcd(p,a) == 1:

            if (pow(a,p-1,p) == 1):

                return True

        else:

            return False

我注意到，要有一个好的费马检验，我需要用多轮a来检查p，这减少了得到费马傻瓜的机会（复合表现得像素数），但也减慢了计算速度。

我的问题是：

有没有办法使此功能更快？还是有其他已知的算法比费马更快？

Answer 1

你可以使用sympy库，它有一个sympy.isprime（）函数，它使用Fermat测试的更好实现（我可能是错的，但想法几乎是一样的）。但是，现在我仍然不知道如何使总时间小于30秒（有时你很幸运，你可以在1秒内生成一个安全Prime，但其他时间它可以达到120秒）