cryptography - 协助寻找密码系统的素数

Question

我是一名大学生，有一项需要找到大素数的作业。教授给了我以下“简单”算法来找到 2 个可能的素数。

生成随机 a 和 p，其中 1 < a < p

确认 gcd(a,p) 是 = 1 -- 这是假设要删除 Carmichael 数 Edit(meant equal to 1)

执行“模幂运算”
如果 x ^ (p-1) % p = 1 其中 x 从零开始递增到 p-1
对于 p 和 a

第 3 步的示例。

假设 p = 5

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

这表明 5 是质数。

我通过这个作业意识到计算素数不是开玩笑。我在上面的算法中看到的问题是，如果我在猜测大数并用模幂来测试它们，我可能会试图将一个大数提高到一个大数。这让我心中产生了疑问。我也研究了确定性有限自动机和埃拉托色尼筛法。有没有人有任何建议来改进给定的算法或提供任何类型的帮助？谢谢你的时间。

Answer 1

您遵循的算法称为 Fermat primality test .但是，你的解释有几个问题:

你说“确认 gcd(a,p) < 1”。这是没有意义的，因为 gcd 永远不会小于 1。您可以检查的是 gcd(a,p)==1。如果它不是 1，则 p 不是素数。这可以检测卡迈克尔数，但可能只有很小的机会这样做。

进行测试的方式是，对于 p 的某个值，您选择 a 的几个随机值并检查是否 a ^ (p-1) % p == 1。如果其中一个不是 1，则 p 是不是总理。您选择的 a 值越多，您的准确性就越高。

您当然不能像您所说的那样检查 x 的所有值 - 因为要检查的值太多了。

有一种快速的方法来执行模幂运算，即使对于大基数和指数也是如此。见 Wikipedia article .您仍然需要一种方法来对大整数执行乘法和取模。

埃拉托色尼筛法仅用于寻找小素数。

此测试可能会错误地确定卡迈克尔数为素数。其他算法如 Rabin-Miller没有这个问题。