АЛГОРИТМЫ ПОИСКА ПРОСТЫХ ЧИСЕЛ

Аннотация

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

Основные определения

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

Определение 1. Простое число – натуральное число ℕ, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

Определение 2. Составное число – натуральное число ℕ, которое не является простым.

Определение 3. Криптография – наука о методах обеспечения конфиденциальности, целостности данных, аутентификации, а также невозможности отказа от авторства.

Определение 4. Вычислительная сложность – функция зависимости объема работы алгоритма от размера входных данных.

Определение 5. Пространственная сложность – функция зависимости объема занимаемой памяти алгоритмом от размера входных данных.

Постановка проблемы

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

Решето Эратосфена

Вычислительная сложность алгоритма:

Пространственная сложность алгоритма:

Описание: Детерминированный алгоритм поиска простых чисел на отрезке от единицы до заданного целого числа n.

Алгоритм: Выпишем последовательно все целые числа из отрезка [2,N], где N — заданное число. Возьмем первое число x₁ из этого списка и вычеркнем все числа кратные (2x_1, 3x₁, 4x₁...) ему. Найдем первое не зачеркнутое число x₂ в списке, большее чем x₁ и повторим операцию вычеркивания кратных чисел. Будем продолжать эти шаги до тех пор, пока это возможно. Таким образом все оставшиеся (не зачеркнутые) числа будут простыми.

Рисунок 1. Описание работы алгоритма. Исключение чисел кратных 2.

Рисунок 2. Описание работы алгоритма. Исключение чисел кратных 2 и 3.

Рисунок 3. Результат работы алгоритма.

Решето Сундарама

Вычислительная сложность алгоритма:

Пространственная сложность алгоритма:

Описание: Детерминированный алгоритм поиска простых чисел на отрезке от единицы до 2N+1, где N - заданное число. Основная идея алгоритма заключается в вычеркивании всех составных чисел из списка, таким образом в нем останутся только простые.

Алгоритм: Выпишем последовательно все целые числа из отрезка [2,N]. Вычеркнем из списка все целые числа вида i+j+2ij<=N, где i, j – всевозможные комбинации целых чисел от 1 до N, причем i<=j. Каждое оставшееся (не зачеркнутое число) умножается на 2 и увеличивается на 1. Таким образом будет получена последовательность простых чисел на отрезке [1, 2N+1].

Решето Аткина

Вычислительная сложность алгоритма:

Пространственная сложность алгоритма:

Описание: Алгоритм поиска простых чисел на отрезке от единицы до заданного числа n. Алгоритм основан на следующих теоремах:

Теорема 1: Пусть n – натуральное число, свободное от квадратов (т.е. не делящееся ни на какой квадрат простого числа) и которое можно представить в виде 1+4ℤ. Тогда, n – просто тогда и только тогда, когда выражение  – нечетно.

Теорема 2: Пусть n–натуральное число, свободное от квадратов (т.е. не делящееся ни на какой квадрат простого числа) и которое можно представить в виде 1+6ℤ. Тогда, n – просто тогда и только тогда, когда выражение  – нечетно.

Теорема 3: Пусть N – натуральное число, свободное от квадратов (т.е. не делящееся ни на какой квадрат простого числа) и которое можно представить в виде 11+12ℤ. Тогда, n – просто тогда и только тогда, когда выражение  – нечетно.

Алгоритм: Выпишем последовательно все целые числа из отрезка [2,N], где N – заданное число. Для каждой пары (x,y):  вычислим значения уравнений (по теореме 1),(по теореме 2) и если x > y: (по теореме 3). Если полученное значение нечетно и его можно представить в виде  , то число либо простое либо кратно квадрату простого числа. Таким образом, чтобы убедиться, что число простое в заключительном этапе необходимо вычеркнуть числа кратные их квадратам.

Сравнение алгоритмов поиска простых чисел.

Рисунок 4. Сравнение алгоритмов поиска просты чисел по вычислительной сложности.

Был проведен сравнительный анализ различных алгоритмов поиска простых чисел, по результатам которого можно построить график (рисунок 4). Нетрудно заметить, что среди тестов, которые подверглись проверке на быстродействие, наиболее эффективным оказалось решето Аткина.

Заключение

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

Список литературы:

1. Atkin A.O.L. and Bernstein D. J. Prime sieves using binary quadratic forms // Mathematics of computation. 2004. P. 1023-1030.