Алгоритмы генерации простых чисел

Введение

Алгоритмы для генерации простых чисел

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

Первичные сита

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

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

Для больших простых чисел, используемых в криптографии, доказуемые простые числа могут быть сгенерированы на основе вариантов теста простоты Поклинтона, а вероятные простые числа – с помощью вероятностных тестов простоты, таких как тест Baillie–PSW или тест Миллера – Рабина. И доказуемые, и вероятные тесты простоты основаны на возведении в степень по модулю. Для дальнейшего снижения вычислительных затрат целые числа сначала проверяются на наличие малых простых делителей с использованием сит, подобных решету Эратосфена, или непосредственного перебора делителей. Целые числа специальных форм, такие как числа Мерсенна или числа Ферма, могут быть эффективно проверены на простоту, если известно простое разложение чисел p − 1 или p + 1.

Сложность

Сито Эратосфена обычно считается самым простым в реализации, но не самым быстрым с точки зрения количества операций для заданного диапазона при больших диапазонах просеивания. В своей обычной стандартной реализации (которая может включать базовую факторизацию колесом для малых простых чисел), оно может найти все простые числа до N за время , в то время как базовые реализации сита Аткина и колесных сит работают за линейное время. Специальные версии сита Эратосфена, использующие принципы сита колес, могут иметь ту же линейную временную сложность. Особая версия сита Аткина и некоторые специальные версии колесных сит, которые могут включать просеивание с использованием методов из сита Эратосфена, могут работать с сублинейной временной сложностью. Следует отметить, что уменьшение асимптотической временной сложности алгоритма не означает, что его практическая реализация будет быстрее, чем алгоритма с большей асимптотической сложностью: если для достижения меньшей асимптотической сложности отдельные операции имеют постоянный фактор увеличения времени, который может быть во много раз больше, чем для более простого алгоритма, то в пределах практических диапазонов просеивания преимущество уменьшенного числа операций для разумно больших диапазонов может никогда не компенсировать эту дополнительную стоимость времени на операцию. Некоторые алгоритмы просеивания, такие как сито Эратосфена с большим количеством факторизации колесом, занимают гораздо меньше времени для меньших диапазонов, чем указывает их асимптотическая временная сложность, поскольку они имеют большие отрицательные постоянные смещения в своей сложности и, следовательно, не достигают этой асимптотической сложности до тех пор, пока не выйдут за пределы практических диапазонов. Например, сито Эратосфена с комбинацией факторизации колесом и предварительной отсеивания с использованием малых простых чисел до 19 использует время примерно в два раза меньше, чем предсказывается для общего диапазона для диапазона 1019, просеивание которого для лучшего из алгоритмов просеивания занимает сотни процессорных лет. Простые наивные сита типа "один большой массив" любого из этих типов сит занимают объем памяти около , что означает, что 1) они сильно ограничены в диапазонах просеивания, которые они могут обрабатывать, объемом доступной оперативной памяти (памяти), и 2) они обычно довольно медленны, поскольку скорость доступа к памяти обычно становится узким местом, ограничивающим скорость больше, чем вычислительная скорость, как только размер массива превышает размер кэша процессора. Обычно реализуемые сегментированные по страницам сита Эратосфена и Аткина занимают объем памяти плюс небольшие буферы сегментов сита, которые обычно имеют размер, достаточный для размещения в кэше процессора; сегментированные по страницам колесные сита, включая специальные вариации сита Эратосфена, обычно занимают гораздо больше места, чем это, на значительный фактор, чтобы хранить необходимые представления колеса; вариация Притчарда сита линейной временной сложности Эратосфена/колесного сита занимает объем памяти . Улучшенная по времени специальная версия сита Аткина занимает объем памяти. Соренсон показывает улучшение колесного сита, которое занимает еще меньше места – для любого . Однако, следует общее наблюдение: чем больше уменьшается объем памяти, тем больше постоянный фактор увеличения стоимости времени на операцию, даже если асимптотическая временная сложность может оставаться прежней, что означает, что версии с уменьшенным объемом памяти могут работать во много раз медленнее, чем версии без уменьшения памяти, на довольно большой фактор.

The sieve of Eratosthenes is generally considered the easiest sieve to implement, but it is not the fastest in the sense of the number of operations for a given range for large sieving ranges. In its usual standard implementation (which may include basic wheel factorization for small primes), it can find all the primes up to N in time while basic implementations of the sieve of Atkin and wheel sieves run in linear time Special versions of the Sieve of Eratosthenes using wheel sieve principles can have this same linear time complexity. A special version of the Sieve of Atkin and some special versions of wheel sieves which may include sieving using the methods from the Sieve of Eratosthenes can run in sublinear time complexity of Note that just because an algorithm has decreased asymptotic time complexity does not mean that a practical implementation runs faster than an algorithm with a greater asymptotic time complexity: If in order to achieve that lesser asymptotic complexity the individual operations have a constant factor of increased time complexity that may be many times greater than for the simpler algorithm, it may never be possible within practical sieving ranges for the advantage of the reduced number of operations for reasonably large ranges to make up for this extra cost in time per operation. Some sieving algorithms, such as the Sieve of Eratosthenes with large amounts of wheel factorization, take much less time for smaller ranges than their asymptotic time complexity would indicate because they have large negative constant offsets in their complexity and thus don't reach that asymptotic complexity until far beyond practical ranges. For instance, the Sieve of Eratosthenes with a combination of wheel factorization and pre culling using small primes up to 19 uses time of about a factor of two less than that predicted for the total range for a range of 1019, which total range takes hundreds of core years to sieve for the best of sieve algorithms. The simple naive "one large sieving array" sieves of any of these sieve types take memory space of about , which means that 1) they are very limited in the sieving ranges they can handle to the amount of RAM (memory) available and 2) that they are typically quite slow since memory access speed typically becomes the speed bottleneck more than computational speed once the array size grows beyond the size of the CPU caches. The normally implemented page segmented sieves of both Eratosthenes and Atkin take space plus small sieve segment buffers which are normally sized to fit within the CPU cache; page segmented wheel sieves including special variations of the Sieve of Eratosthenes typically take much more space than this by a significant factor in order to store the required wheel representations; Pritchard's variation of the linear time complexity sieve of Eratosthenes/wheel sieve takes space. The better time complexity special version of the Sieve of Atkin takes space Sorenson shows an improvement to the wheel sieve that takes even less space at for any However, the following is a general observation: the more the amount of memory is reduced, the greater the constant factor increase in the cost in time per operation even though the asymptotic time complexity may remain the same, meaning that the memory reduced versions may run many times slower than the non memory reduced versions by quite a large factor.