print - python get prime numbers

Probando la primalidad de primos probables fuertes

Question

Usando la versión probabilística de la prueba de Miller-Rabin, he generado una lista de números primos probables medianos-grandes (200-300 dígitos). Pero probablemente no sea lo suficientemente bueno! Necesito saber que estos números son primos. ¿Existe una biblioteca, preferiblemente envuelta o envolvente en Python, que implemente uno de los algoritmos de comprobación de primalidad más eficientes?

Alternativamente, ¿alguien sabe dónde puedo encontrar una descripción clara , detallada y completa de ECPP (o un algoritmo igualmente rápido) que no suponga una gran cantidad de conocimiento previo?

Actualización: he encontrado una implementación Java de otra prueba, APRT-CLE, que demuestra de manera concluyente la primalidad. Verificó un candidato principal de 291 dígitos en menos de 10 minutos en un procesador atómico. Todavía espero algo más rápido, pero esto parece un comienzo prometedor.

Answer 1

Como un algoritmo que da una prueba de primalidad polinomial confiable, considere AKS . Hay un artículo anterior de SO que hace referencia a implementaciones y presentaciones del algoritmo.

Answer 2

Descubrí que la biblioteca y el lenguaje Pari / GP usan APR-CL para demostrar la primalidad, que en realidad es el algoritmo preferido para los números en este rango de tamaño, como resulta. GP demuestra un primer candidato de 291 dígitos en menos de 20 segundos en un procesador atómico, que es suficiente para mis necesidades, y viene con una biblioteca de CA a la que puedo acceder usando 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

También podría usar el módulo instant . Aquí hay una función c simple que ejecuta una cadena a través del analizador de pari y devuelve el resultado como una cadena:

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

Lo anterior también se puede utilizar como la base de una extensión CPython adecuada.