Самый эффективный алгоритм генерации случайных простых чисел в диапазоне бит

Question

NTL/ZZ.h имеет функцию, которая генерирует для вас случайный Prime ZZ номер (ZZ RandomPrime_ZZ (длинный, длинный)), мне было интересно, если кто-либо из вас знаете, какой алгоритм использует NTL для достижения этого. В противном случае, пожалуйста, оцените хороший алгоритм, который, как вы знаете, эффективен. Под «в диапазоне бит» я имею в виду генерировать простые числа из x бит в зависимости от параметра (например, 2048 бит).

Answer 1

NTL (как минимум, с версии 9.20) генерирует случайные нечетные числа с соответствующей длиной бита и тестирует их с заданным числом тестов Миллера-Рабина (по умолчанию 10). Если они тестируются как составные, они начинаются, иначе он возвращает число (вероятный-премьер).

GenPrime делает то же самое, но вместо того, чтобы давать ему несколько тестов, вы даете ему число, указывающее максимальную вероятность отказа, которую вы готовы принять (значение по умолчанию 80 означает, что он может терпеть неудачу до одного раза каждые 2^80 ≈ 10^24 в среднем. Он использует глубокий результат Damgård, Landrock, & Pomerance (1993), чтобы вычислить количество необходимых тестов.