强可能素数的素数证明

Question

使用Miller-Rabin测试的概率版本，我生成了一个中型(200-300位数)可能素数的列表。但很可能还不够好！我需要知道这些数字是质数。是否有一个库--最好是用Python包装或包装--实现一种更有效的素数验证算法？

或者，有没有人知道我在哪里可以找到一个清晰，详细，完整的描述ECPP (或类似的快速算法)，而不是假定了大量的先验知识？

更新:我发现了另一种测试的Java实现，APRT，最终证明它是最原始的。它在原子处理器上用不到10分钟的时间验证了291位数的主候选人.仍然希望能有更快的发展，但这似乎是一个很有希望的开端。

Answer 1

作为给出一个可靠的多项式素数检验的算法，考虑AKS。有一个较老的所以文章引用该算法的实现和表示。

Answer 2

我发现Pari/GP库和语言使用APR来证明素数，这实际上是这个大小范围内数字的首选算法。GP在一个原子处理器上证明了一个291位的候选素数在20秒以内，这足以满足我的需要，它附带了一个c库，我可以使用ctype访问它。

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扩展的基础。