Оптимизация теста Ферма на первичность для большого простого числа (приложение DHKE)

Question

Итак, для DHKE мне нужно сгенерировать большое простое число g (> 500 бит в данном случае), а затем вычислить N = 2g + 1, а затем проверить, является ли N простым. Повторяйте процесс, пока не будет найдено такое N.

Чтобы выполнить sh, я генерирую случайное число g, запускаю fermatTest для него, а затем запускаю fermatTest для N. Однако я заметил, что время выполнения очень медленное (иногда программа занимает минуты)

Вот моя реализация теста Ферма на произвольных числах:

def fermatTest(p):
    for i in range(5):   # probability of getting a fool: 1/32
        a = secrets.randbelow(p)      
        if gcd(p,a) == 1:
            if (pow(a,p-1,p) == 1):
                return True
        else:
            return False

Я заметил, что для хороший тест Ферма, мне нужно проверить p с несколькими раундами a, которые уменьшают вероятность получения дурака Ферма (составной ведет себя как простое число), но также замедляют вычисления.

Мои вопросы:

Есть ли способ сделать эту функцию быстрее? Или есть другие известные алгоритмы, которые быстрее, чем Ферма?

Answer 1

Вы можете использовать библиотеку sympy, которая имеет функцию sympy.isprime (), которая использует лучшую реализацию теста Ферма (я могу ошибаться, но идея почти такая же). Тем не менее, сейчас я все еще не знаю, как сделать общее время менее 30 секунд (иногда вам повезло, что вы можете сгенерировать безопасный прайм в течение 1 секунды, но в другое время это может быть до 120 секунд)