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

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

Для относительно небольших чисел можно просто применить судебное отделение каждому последующему нечетное число. Первичные сита почти всегда быстрее.

Prime сита

Решето простых чисел или решето простых чисел - это быстрый алгоритм поиска простых чисел. Есть много простых сит. Простой сито Эратосфена (250-е гг. До н. Э.) сито Сундарама (1934), еще быстрее, но сложнее сито Аткина^[1], и различные колесные сита^[2] наиболее распространены.

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

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

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

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

Сложность

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

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

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

Смотрите также

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

Рекомендации

1. Аткин, А .; Бернштейн, Д. Дж. (2004). «Первичные сита с использованием двоичных квадратичных форм» (PDF). Математика вычислений. 73 (246): 1023–1030. Дои:10.1090 / S0025-5718-03-01501-1.
2. Причард, Пол (1994). Улучшенные сита с добавлением простых чисел. Симпозиум по алгоритмической теории чисел. С. 280–288. CiteSeerX  10.1.1.52.835.
3. Соренсон, Дж. П. (1998). Торговля временем на пространство в решетах простых чисел. Конспект лекций по информатике. 1423. С. 179–195. CiteSeerX  10.1.1.43.9487. Дои:10.1007 / BFb0054861. ISBN  978-3-540-64657-0.