Proving the primality of strong probable primes

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.