Перечисление больших (20-значных) [вероятных] простых чисел

Question

Учитывая A, порядка 10 ^ 20, я бы хотел быстро получить список первых нескольких простых чисел, превышающих A. Хорошо, мои потребности не совсем точны - это нормально, если иногда составнойчисло заканчивается в списке.

Какой самый быстрый способ перечислить (вероятные) простые числа больше A?

Есть ли более быстрый способ, чем пошаговое выполнение всех целых чисел больше A (кроме очевидных кратных, скажем, 2 и 3) и выполнения теста на простоту для каждого из них?Если нет, и единственный метод состоит в том, чтобы проверить каждое целое число, какой тест на первичность я должен использовать?

Answer 1

Отличный вопрос. Это все еще не доказано в полиномиальное время (полиномиальное количество цифр, здесь 20) - это был проект Finding Primes Polymath, в котором участвовали несколько математиков (включая Полевых Медалистов Теренса Тао и Тима Гауэрса!) пытался придумать алгоритм, но проект, похоже, пока не дал конкретных результатов.

В любом случае, есть несколько вещей, которые вы можете сделать. Один из них, как вы и другие указали, состоит в том, чтобы попробовать каждое число и проверить, является ли оно простым, с помощью быстрого теста на простоту, такого как Миллер-Рабин . По известным теоретико-числовым эвристикам (основанным на теореме о простых числах ), "вероятность" числа около n, являющегося простым, составляет около 1 / ln (n), поэтому при 10 ^ 20, около в каждых 46 числах будут простые числа. Поэтому, если вам нужно k 20-значных чисел, вы запустите тест Миллера-Рабина для примерно 50 тыс. Чисел.

Второй подход, который я думаю может быть быстрее, если вы делаете это для многих А (не задумывался тщательно), состоит в том, чтобы вместо этого использовать сито , как Сито Эратосфена . Если вам нужно k простых чисел, создайте массив из примерно 50 000 чисел (или больше, чтобы быть в безопасности) и просейте их. Вы начнете с предварительно вычисленного списка простых чисел, меньших некоторого числа. (10 ¹⁰ , чтобы быть совершенно правильным, но, поскольку вы готовы допустить некоторые составные числа, подойдет меньший список простых чисел, например, проверка с помощью первых 50 миллионов простых чисел , убедитесь, что у ваших чисел нет главных факторов ниже 982 451 653, и их не так много.)

Третий подход - найти чью-либо реализацию для этой проблемы. :-) Например, есть веб-страница с заданным номером, находит следующее простое число или находит следующие десять простых чисел . Если вы используете его в Интернете, то вам, вероятно, придется скопировать его вручную, но также доступен исходный код .

Answer 2

Есть ли более быстрый способ, чем ступить через все целые числа больше чем A (кроме очевидных кратных скажем, 2 и 3) и выполнение тест на простоту каждого из них?

Нет, нет способа узнать, является ли число простым без теста на простоту.

Однако вы можете очень быстро выполнить вероятностный тест на простоту, такой как Миллер-Рабин для любого числа. Это безопасный и общепринятый метод поиска больших простых чисел. Поскольку простые числа относительно многочисленны, у вас не будет проблем с поиском простых чисел в любом диапазоне, используя этот метод. Просто используйте проверенную и эффективную реализацию Миллера-Рабина, и все будет в порядке.

Answer 3

Простые числа - тихие частые числа. Частота простых чисел - это log (n), что означает, что в среднем каждое 46-е число является простым, где n = 10 ^ 20. Это означает, что проверка каждого числа на простоту не является такой затратами.

Answer 4

Самое лучшее, что вы можете сделать, - это найти разумного кандидата, а затем протестировать его. Тест Миллера-Рабина отвечает вашему требованию высокой вероятности того, что число простое, и вы можете снизить вероятность скольжения составного до более или менее произвольного уровня в зависимости от того, сколько итераций вы используете.