使用Miller-Rabintesting的概率版本，我生成了一个大中（200-300位）的可能素数列表。 但可能不够好！ 我需要知道这些数字是素数。 有没有一个库（最好是用Python包装或包装），实现了一个更高效的素数validationalgorithm？
另外，有没有人知道我在哪里可以find一个清晰 ， 详细 ， 完整的ECPP（或类似的快速algorithm）的描述，不承担大量的先验知识？
更新：我发现了另一个testingAPRT-CLE的Java实现 ，最终certificate了素数。 它在一个primefaces处理器上在10分钟内核实了一个291位的主要候选人。 仍然希望更快一些，但这似乎是一个有希望的开始。
作为给出可靠的多项式素性测试的算法，考虑AKS 。 有一篇较早的SO文章引用了该算法的实现和演示。
我发现Pari / GP库和语言使用APR-CL来证明素数，事实证明这实际上是数字在这个大小范围内的首选算法。 GP在原子处理器上20秒内证明了一个291位数的候选素数，这足以满足我的需求，而且它还带有可以使用ctypes访问的ac库。
import ctypes def pari_isprime(self, n): try: pari = ctypes.cdll.LoadLibrary("libpari.so") except OSError: print "pari_isprime: couldn't load libpari!" exit() int(n) pari.pari_init(4000000, 2) ret = bool(pari.isprime(pari.gp_read_str(str(n)))) pari.pari_close() return ret 我也可以使用instant模块。 下面是一个简单的c函数，它通过pari的解析器运行一个字符串，并以字符串形式返回结果：
from instant import inline runpari_code = """ PyObject* runpari(PyObject *args) { pari_init(40000000, 2); char *pari_code; char *outstr; if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple outstr = GENtostr(gp_read_str(pari_code)); pari_close(); return Py_BuildValue("s", outstr); } """ runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari'])
以上也可以作为CPython扩展的基础。