我是一名大学生,有一项需要找到大素数的作业。教授给了我以下“简单”算法,以找到 2 个可能的素数。
- 生成随机 a 和 p 其中 1 < a < p
- 确认 gcd(a,p) 是 = 1 - 这是假设删除 Carmichael 数字编辑(意味着等于 1)
- 如果 x ^ (p-1) % p = 1 则执行“模幂运算”,其中 x 从零开始,对于 p 和 a 都递增到 p-1
第三步的例子。
假设 p = 5
1^4 %5 = 1
2^4 %5 = 1
3^4 %5 = 1
4^4 %5 = 1
这表明 5 是素数。
我通过这个作业意识到计算素数不是开玩笑。我在上述算法中看到的问题是,如果我猜测大数并使用模幂来测试它们,我可能会尝试将大数提升为大数。这让我心中产生了疑问。我也研究了确定性有限自动机和埃拉托色尼筛法。有没有人有任何建议来改进给定的算法或提供任何帮助?谢谢你的时间。