大素数的Fermat素性检验的优化(DHKE应用)

Question

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

为此，我生成一个随机数g，在其上运行fermatTest，然后在N上运行fermatTest。然而，我注意到运行时间非常慢(有时程序需要几分钟)

这是我对任意数的Fermat测试的实现：

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

我注意到，为了有一个好的Fermat测试，我需要用多轮的a来检查p，这会减少得到Fermat的愚蠢(复合行为类似于素数)的机会，但也会减慢计算速度。

我的问题是：

有没有办法让这个函数更快呢？或者还有其他已知的算法比Fermat更快？

Answer 1

你可以使用渐近库，它有一个sympy.isprime()函数，它使用了费马测试的一个更好的实现(我可能错了，但想法几乎是一样的)。然而，现在我仍然不知道如何将总时间减少到30秒以下(有时你很幸运，你可以在1秒内生成一个安全的Prime，但其他时间可以长达120秒)