Доказательство простоты сильных вероятных простых чисел

Question

Используя вероятностную версию теста Миллера-Рабина, я составил список средних (200-300 цифр) возможных простых чисел. Но, вероятно, не достаточно хорош! Мне нужно знать, что эти числа простые. Существует ли библиотека - предпочтительно упакованная или обертываемая в Python - которая реализует один из более эффективных алгоритмов доказательства первичности?

Кроме того, кто-нибудь знает, где я могу найти четкое, подробное и полное описание ECPP (или аналогичного быстрого алгоритма), которое не предполагает большого количества предварительных знаний?

Обновление: я нашел реализацию Java другого теста, APRT-CLE, который убедительно доказывает первичность. Он проверил 291-значный главный кандидат менее чем за 10 минут на процессоре Atom. Все еще надеемся на что-то более быстрое, но это кажется многообещающим началом.

Answer 1

В качестве алгоритма, который дает надежный тест на полиномиальную простоту, рассмотрим AKS. Есть более старая статья SO, ссылающаяся на реализации и представления алгоритма.

Answer 2

Я обнаружил, что библиотека и язык Pari/GP используют APR-CL для доказательства простоты, что на самом деле является предпочтительным алгоритмом для чисел в этом диапазоне размеров, как оказалось. GP доказывает простое число кандидатов в 291 цифру менее чем за 20 секунд на процессоре Atom, что достаточно для моих нужд, и он поставляется с библиотекой ac, к которой я могу получить доступ, используя 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.