Proving the primality of strong probable primes

Using the probabilistic version of the Miller-Rabin test, I have generated a list of medium-large (200-300 digit) probable primes. But probable ain't good enough! I need to know these numbers are prime. Is there a library -- preferably wrapped or wrappable in Python -- that implements one of the more efficient primality proving algorithms?

Alternatively, does anyone know where I can find a clear, detailed, and complete description of ECPP (or a similarly fast algorithm) that does not assume a great deal of prior knowledge?

Update: I've found a Java implementation of another test, APRT-CLE, that conclusively proves primality. It verified a 291-digit pri开发者_开发百科me candidate in under 10 minutes on an atom processor. Still hoping for something faster, but this seems like a promising start.

As an algorithm that gives a reliable polynomial primality test, consider AKS. There is an older SO article referencing implementations and presentations of the algorithm.

I've found that the Pari/GP library and language use APR-CL to prove primality, which is actually the preferred algorithm for numbers in this size range, as it turns out. GP proves a 291-digit candidate prime in under 20 seconds on an atom processor, which is sufficient for my needs, and it comes with a c library that I can access using 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

I could also use the instant module. Here's a simple c function that runs a string through pari's parser and returns the result as a string:

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'])

The above can also be used as the basis of a proper CPython extension.