时间戳

首页 > 解决方案 > 大素数的费马素性检验优化（DHKE 应用）

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

问题描述

所以对于DHKE，我需要生成一个大素数g（本例中> 500位），然后计算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

我注意到要进行良好的费马测试，我需要用多轮 a 来检查 p，这减少了得到费马傻瓜的机会（复合行为像素数），但也会减慢计算速度。

我的问题是：

有没有办法让这个功能更快？还是有其他已知算法比 Fermat 更快？

标签： pythonoptimizationcryptographymodular-arithmetic

解决方案

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

推荐阅读