证明强可能素数的素性
我用米勒-拉宾测试的概率版本生成了一些中等到大型（200-300位数）的可能是素数的数字。不过，可能的素数不够好！我需要确认这些数字确实是素数。有没有什么库，最好是可以在Python中使用的，能实现一些更高效的素数证明算法？
另外，有人知道哪里可以找到一个清晰、详细、并且完整描述ECPP（或者类似快速算法）的资料吗？希望这些资料不需要太多的前置知识。
更新：我找到了一种Java实现的另一种测试方法，APRT-CLE，它可以确凿地证明一个数字是否是素数。它在不到10分钟的时间内验证了一个291位的素数候选者，运行在一个原子处理器上。虽然我还是希望能找到更快的方案，但这看起来是一个不错的开始。
2 个回答
7
我发现Pari/GP这个库和语言使用APR-CL算法来证明一个数字是否是质数。其实，这个算法在处理这种大小的数字时是最推荐的。GP可以在不到20秒的时间内，在一个Atom处理器上证明一个291位的候选质数，这对我来说已经足够了。而且它还附带一个C语言库，我可以通过ctypes来使用。
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扩展的基础。