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

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

21 голосов
/ 20 января 2011

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

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

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

Ответы [ 2 ]

9 голосов
/ 20 января 2011

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

6 голосов
/ 23 января 2011

Я обнаружил, что библиотека и язык 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.

...