使用 Miller-Rabin 检验的概率版本,我生成了一个中大型(200-300 位)可能素数的列表。但可能还不够好!我需要知道这些数字是素数。是否有一个库——最好是用 Python 封装或可封装——实现一种更有效的素性证明算法?
或者,有谁知道我在哪里可以找到关于 ECPP(或类似的快速算法)的清晰、详细和完整描述不需要大量的先验知识?
更新:我找到了 Java implementation另一个测试,APRT-CLE,最终证明素性。它在原子处理器上不到 10 分钟就验证了一个 291 位数的主要候选者。仍然希望更快,但这似乎是一个充满希望的开始。
最佳答案
作为提供可靠多项式素性检验的算法,请考虑 AKS .有一个older SO article引用算法的实现和演示。
关于python - 证明强可能素数的素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4752190/