Генерация простых чисел

В вычислительной теории чисел различные алгоритмы позволяют эффективно генерировать простые числа . Они используются в различных приложениях, например, в хешировании , криптографии с открытым ключом и поиске простых чисел в больших количествах.

Для относительно небольших чисел можно просто применить пробное деление к каждому последующему нечетному числу . Первичные сита почти всегда работают быстрее. Отсеивание простых чисел — это самый быстрый из известных способов детерминированного подсчета простых чисел. Существует несколько известных формул, позволяющих вычислить следующее простое число, но не существует известного способа выразить следующее простое число через предыдущие простые числа. Кроме того, не существует известных эффективных общих манипуляций и/или расширений некоторых математических выражений (даже таких, включая более поздние простые числа), которые детерминированно вычисляют следующее простое число.

Премьер-сита

Решето простых чисел или решето простых чисел — это быстрый тип алгоритма поиска простых чисел. Есть много простых сит. Простое решето Эратосфена (250-е гг. до н.э.), решето Сундарама (1934 г.), еще более быстрое, но более сложное решето Аткина. (2003) и различные колесные сита. являются наиболее распространенными.

Сито простых чисел работает путем создания списка всех целых чисел до желаемого предела и постепенного удаления составных чисел (которые оно генерирует напрямую), пока не останутся только простые числа. Это наиболее эффективный способ получить большой диапазон простых чисел; однако для поиска отдельных простых чисел прямые тесты на простоту. более эффективными являются . Кроме того, на основе формализма сита некоторые целочисленные последовательности (последовательность A240673 в OEIS строятся ), которые также можно использовать для генерации простых чисел в определенных интервалах.

Большие простые числа

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

Целые числа специальных форм, такие как простые числа Мерсенна или простые числа Ферма , можно эффективно проверить на простоту, если факторизация простых чисел p - 1 или p известна + 1.

Сложность

Решето Эратосфена вообще считается самым простым в реализации ситом, но оно не является самым быстрым в смысле количества операций на заданный диапазон при больших диапазонах просеивания. В своей обычной стандартной реализации (которая может включать базовую факторизацию колеса для маленьких простых чисел) он может найти все простые числа до N за время. $O(N\log \log N),$ в то время как базовые реализации сита Аткина и колесных сит работают в линейном времени $O(N)$. Специальные версии Решета Эратосфена, использующие принципы колесного сита, могут иметь такую ​​же линейную структуру. $O(N)$ временная сложность. Специальная версия Решета Аткина и некоторые специальные версии колесных сит, которые могут включать в себя просеивание с использованием методов Решета Эратосфена, могут работать с сублинейной временной сложностью. $O(N/\log \log N)$. Обратите внимание, что тот факт, что алгоритм уменьшил асимптотическую временную сложность, не означает, что практическая реализация работает быстрее, чем алгоритм с большей асимптотической временной сложностью: если для достижения этой меньшей асимптотической сложности отдельные операции имеют постоянный коэффициент увеличения временной сложности. это может быть во много раз больше, чем для более простого алгоритма, но в пределах практических диапазонов просеивания никогда не будет возможности компенсировать эти дополнительные затраты времени на операцию за счет уменьшенного количества операций для достаточно больших диапазонов.

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

Простые наивные сита любого из этих типов сит «одного большого массива» занимают в памяти около $O(N)$Это означает, что 1) они очень ограничены в диапазонах просеивания, которые они могут обрабатывать, объемом доступной оперативной памяти (памяти) и 2) что они обычно довольно медленны, поскольку скорость доступа к памяти обычно становится узким местом скорости больше, чем скорость вычислений, как только размер массива превышает размер кэша ЦП. Обычно реализованные постраничные сегментированные сита как Эратосфена, так и Аткина занимают пространство $O(N/\log N)$ плюс небольшие буферы сегментов сита, размер которых обычно соответствует размеру кэша ЦП; сегментированные постранично сегментированные колесные сита, включая специальные варианты Решета Эратосфена, обычно занимают гораздо больше места, чем это, в значительной степени, чтобы хранить необходимые представления колес; Вариант Причарда линейного решета временной сложности Эратосфена/колесного решета принимает $O(N^{1/2}\log \log N/\log N)$ космос. Специальная версия решета Аткина с лучшей временной сложностью требует места. $N^{1/2+o(1)}$. Соренсон показывает усовершенствование колесного сита, которое занимает еще меньше места при $O(N/((\log N)^{L}\log \log N))$ для любого $L>1$. Однако есть общее наблюдение: чем больше уменьшается объем памяти, тем больше постоянный коэффициент увеличения затрат времени на операцию, даже если асимптотическая временная сложность может остаться прежней, а это означает, что версии с уменьшенным объемом памяти могут работают во много раз медленнее, чем версии без сокращения памяти, в довольно большом разы.

См. также

• Формула простых чисел