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

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

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

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

Ответ 1

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

Ответ 2

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

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.