УДК 004.021
Кузьменко Д.Е., Мизин Д.С.
Анализ алгоритмов получения простых чисел
Севастопольский национальный технический университет
This work is about the calculation algorithms and applicability of the prime numbers.
Эта работа об алгоритмах получения и применимости простых чисел.
Ключевые слова: простые числа, алгоритм.
Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту [1]. Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают решето Эратосфена, решето Сундарама и решето Аткина. Рассмотрим первый и третий алгоритмы.
Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число. Сложность алгоритма — О(n log log n).
В 1999 году Аткин и Бернштейн предложили новый метод отсеивания составных чисел, получивший название решета Аткина. Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x2+y2], S[3x2+y2], а также, если x > y, то и в S[3x2−y2]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых. В качестве заключительного этапа пройдемся по предположительно простым номерам последовательно и вычеркнем кратные их квадратам. Из описания видно, что сложность решета Аткина пропорциональна О(n), а не О(n log log n), как у алгоритма Эратосфена.
Однако, важно заметить, что множитель log log n растет крайне медленно. Например, log log 1010000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых чисел не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена и не тратить время разработчиков попусту на реализацию более сложного алгоритма. Однако при поиске простых чисел на больших интервалах (от 232) игра стоит свеч. Оптимизации и решето Аткина могут ощутимо повысить производительность в этом случае.
Именно большие простые числа (порядка 10300) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ вихрь Мерсенна) [2].
Литература:
1. Гальперин Г. Просто о простых числах — Квант, № 4. — С. 9-14,38.
2. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с.