优化大素数的费马素数测试（DHKE 应用程序）

Question

所以对于DHKE，我需要生成一个大素数g（在这种情况下> 500位），然后计算N = 2g+1，然后测试N是否为素数。重复这个过程，直到找到这样的 N。

为了完成这个，我生成了一个随机数g，运行 fermatTest 就可以了，然后运行 fermatTest 就可以了。但是，我注意到运行时间非常慢（有时程序需要几分钟）

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

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.isprime() 函数的 sympy 库，该函数使用更好的 Fermat 测试实现（我可能是错的，但想法几乎相同）。但是，现在我仍然不知道如何使整体时间小于 30 秒（有时你很幸运可以在 1 秒内生成 Safe Prime，但其他时间可能长达 120 秒）

优化大素数的费马素数测试（DHKE 应用程序）

Optimization for Fermat Primality test for large prime number (DHKE application)

python

optimization

cryptography

modular-arithmetic