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 ctypesdef 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 inlinerunpari_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.