Способы проверки простоты числа

Еще раз о поиске простых чисел

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].

Если теперь нам нужно найти все простые на достаточно широком интервале, то первым побуждением, наверное, будет протестировать каждое число из интервала индивидуально. К счастью, если у нас достаточно памяти, можно использовать более быстрые (и простые) алгоритмы решета. В этой статье мы обсудим два из них: классическое решето Эратосфена, известное еще древним грекам, и решето Аткина, наиболее совершенный современный алгоритм этого семейства.

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

Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.

Много времени можно сэкономить, если заметить, что, поскольку у составного числа, меньшего n, по крайней мере один из делителей не превосходит , процесс высевания достаточно закончить на . Вот анимация решета Эратосфена, взятая с Википедии:

Еще немного операций можно сэкономить, если — по той же причине — начинать вычеркивать кратные k, начиная не с 2k, а с номера k 2 .

Реализация примет следующий вид:

Эффективность решета Эратосфена вызвана крайней простотой внутреннего цикла: он не содержит условных переходов, а также «тяжелых» операций вроде деления и умножения.

Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса

так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).

Оптимизация и параллелизация

Первую оптимизацию решета предложил сам Эратосфен: раз из всех четных чисел простым является только 2, то давайте сэкономим половину памяти и времени и будем выписывать и высеивать только нечетные числа. Реализация такой модификации алгоритма потребует лишь косметических изменений (код).

Более развитая оптимизация (т. н. wheel factorization) опирается на то, что все простые, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29. Чтобы найти все простые числа до n, вычислим предварительно (опять же при помощи решета) все простые до . Теперь составим восемь решет, в каждое из которых будут входить элементы соответствующей арифметической прогрессии, меньшие n, и высеем каждое из них в отдельном потоке. Все, можно пожинать плоды: мы не только понизили потребление памяти и нагрузку на процессор (в четыре раза по сравнению с базовым алгоритмом), но и распараллелили работу алгоритма.

Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.

Сегментация

Что же делать, если, несмотря на все наши ухищрения, оперативной памяти не хватает и алгоритм безбожно «свопится»? Можно заменить одно большое решето на последовательность маленьких ситечек и высевать каждое в отдельности. Как и выше, нам придется предварительно подготовить список простых до , что займет O(n ½-ε ) дополнительной памяти. Простые же, найденные в процессе высевание ситечек, нам хранить не нужно — будем сразу отдавать их в выходной поток.

Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.

Решето Эратосфена и однострочники

На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.

Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.

Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.

Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.

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

Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:

Вторая проблема: массивы в PHP ужасны по накладным расходам памяти. У меня на 64-битной системе каждый элемент $S из кода выше съедает по 128 байт. Как обсуждалось выше, необязательно держать сразу все решето в памяти, можно обрабатывать его порционно, но все равно такие расходы дóлжно признать недопустимыми.

Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!

Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.

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

В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.

Теорема. Пусть n — натуральное число, которое не делится ни на какой полный квадрат. Тогда

1. если n представимо в виде 4k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 4x 2 +y 2 = n нечетно.
2. если n представимо в виде 6k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 +y 2 = n нечетно.
3. если n представимо в виде 12k-1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 −y 2 = n, для которых x >y, нечетно.

C доказательством можно ознакомиться в [4].

Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).

Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.

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

Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.

Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.

Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).

О логарифме логарифма

На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.

P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник

Проверка простых чисел

Общее

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

Быстрые тесты для малых чисел и вероятно простые числа

Малые простые числа

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

Малая теорема Ферма

Французский математик Пьер Ферма в 17 веке выдал закономерность, которая лежит в основе почти всех методов проверки на простоту.

Малая теорема Ферма — Если P простое и A — любое целое, то A P = A (mod P). Если P не делит А, то А P-1 = 1 (mod P). На основе такой теоремы, можно создать мощный алгоритм на простоту:

• Тест Ферма: Для n > 1 выбираем a > и вычисляем A n-1 mod n, если результат не 1, то n составное число, если 1, то n — слабо возможно простое по основанию a (a-PRP)

Часть чисел проходящие Тест Ферма являются составными, и их называют псевдопростыми.

Тест Рабина-Миллера

Можно улучшить тест Ферма, заметив, что если n — простое нечетное, то для 1 есть только два квадратных корня по модулю n: 1 и -1. По этому квадратный корень из A n-1 , A (n-1)/2 равен минус или плюс еденице. Если (n-1)/2 опять нечетно, то можно снова извлечь корень и тд. Первый вариант алгоритма определяет только одно деление:

• Тест Леманна: Если для любого целого числа А меньшего n не выполняется условие A (n-1)/2 = ± 1 (mod n), то число n — составное. Если это условие выполнено, то число n — возможно простое с вероятностью ошибки не больше 50%.
• Тест Рабина-Миллера: Запишем (n-1) в виде 2 s d, где d нечетно, а s — неотрицательно: n называют сильно возможно простым по основанию A (A-SPRP), если реализуется одно из двух условий:
  • A d = 1 (mod n)
  • (A d ) 2 r = -1 (mod n), для любого неотрицательного r -2t

  Объединение тестов

  Классические тесты

  Проверки чисел вида n + 1

  Тест заключается в том, что мы должны знать частичное или полное разложение на множители числа n — 1. Разложение на множители n — 1 просто найти, если n имеет определенный вид.

  • Тест Лукаса: N ≥ 3. Если для каждого простого q, делящего n — 1 есть целое А такое что:
    • A n-1 = 1 (mod n) и
    • A (n-1)/q ≠ 1 (mod n), то n — простое

  Для такой проверки нужно знать полное разложение n — 1 на простые множители. Более мощная версия определяет знание не полного, а частичного разложения n — 1 на простые множители. Такой вариант алгоритма был выдан Поклингтоном в 1914 году.

  • Тест Поклингтона: N ≥ 3 и n = FR + 1 (F делит n-1), причем F > R, НОД (F,R) = 1 и известно разложение F на простые множители. Тогда, если для любого простого q, делящего F есть такое целое A > 1, что:
    • A n-1 = 1 (mod n) и
    • НОД (A (n-1)/q — 1, n) = 1
  • Теорема Пепина: пусть F_n это n-е число Ферма и n > 1, тогда F_n — простое тогда и только тогда, когда 3 (F_n — 1)/2 = 1 (mod F_n
  • Теорема Прота: Пусть n = h × 2 k + 1, причем 2 k > h. Если есть такое целое A, что A (n-1)/2 = -1 (mod n), то n — простое

  На основе теоремы Прота было найдено пятое по величине из известных простых чисел — 28433 × 2 7830457

  Проверки чисел вида n — 1

  Здесь рассмотрим числа только определенного вида. 7 из первых 10 позиций по самым большим известным простым числам были найдены с помощью чисел Мерсенна. Числа Мерсенна называют числа вида 2 s -1.

  Лукасом и Лемером в 1930 году было создано следующее утверждение: пусть s — простое, тогда число Мерсенна n = 2 s — 1 является простым тогда, когда S (n — 2) = 0, где S(0) = 4 и S(k+1) = S(k) 2 — 2 (mod n). На основе такого факта можно создать проверку на простоту, которая точно скажет нам, является ли для заданного s число Мерсенна простым.

  • Тест Лукаса-Лемера:
    • С помощью пробного деления проверяем, является ли данное s простым, если нет, то получившееся число Мерсенна — составное
    • Задаем S(0) = 4
    • Для k от 1 до s — 2 вычисляем S(k) = S(k-1) 2 — 2 (mod n)
    • Если в результате получился 0, то число Мерсенна простое

  Неоклассические алгоритмы ARP и ARP-CL

  Можно рассматривать числа в виде n 2 + n + 1 или n 2 — n + 1. А можно рассмотреть число вида n m — 1 для больших m. Тогда любое просто число q такое, что q — 1 делит m, по малой теореме Ферма будет делить n m — 1.

  Было представлено, что всегда существует целое число m:

  Эллиптические кривые: ECPP

  Современные вариант проверок на простоту основан на теореме Поклингтона, но для эллиптических кривых. Смысл алгоритма заключается в переходе от групп порядка n — 1 и n + 1 к достаточно большему диапазону размеров групп.

  В 2002 году летом индийские математики Аграавал, Саксен и Кайал нашли полиномиальный детерминированный алгоритм проверки числа на простоту. Их метод основан на версии малой теоремы Ферма:

  • Теорема: Пусть A и P взаимно простые целые числа и P > 1. Число P является простым, когда (x — a) p = (x p — a) (mod p)
  • Доказательство: Если p — простое, то p делит биномиальные коэффициенты _pC_r для r = 1,2 ..p-1. Пусть p — составное, и пусть q — простой делитель p. Пусть q k максимальная степень q которая делит p. Тогда q k не делит _pC_r и взаимно просто с A p-q . Отсюда, коэффициент перед x q в левой части требуемого равенства не равен нулю, а в правой равен. Алгоритм для числа n ≥ 23 (странное число получается из одного из требований для корректной работы алгоритма)

  Итоги

  Тест	Тип теста	Где используется
  Пробное деление	детерминированный	Из-за большой вычислительной сложности в чистом виде не используется. Пробное деление на маленькие простые числа реализуется во многих тестах как один из шагов
  Ферма	вероятностный	В чистом виде не реализуется. Может быть одним из первых шагов на проверку простоты для очень больших чисел
  Леманна	верляьнлсьный	Не используется
  Рабина-Миллера	вероятностный	В чистом виде может реализовываться в криптосистемах с открытым ключом для реализации простых ключей длиной 512, 1024 и 2048 бит.
  Миллера	детерминированный	На практике не используется, так как пока не доказана расширенная гипотеза Римана
  Лукаса	детерминированный	Для получения больших простых чисел определенного вида
  Поклингтона	детерминированный	Для получения больших чисел с частично известной факторизацией n — 1
  Петина	детерминированный	Для получения больших простых чисел Ферма
  Прота	детерминированный	Для получения больших простых чисел определенного вида
  Лукаса-Лемера	детерминированный	Для получения больших простых чисел Мерсенна
  APR	детерминированный	В качестве детерминированной быстрой проверки на простоту
  ECPP	детерминированный	В качестве детерминированной быстрой проверки на простоту
  AKS	детерминированный	В качестве детерминированной полиномиальной проверки на простоту

  Из таблицы видно, что разные методы проверки на простоту служат для двух целей:

  • для получения очень больших целый чисел
  • для генерации простых чисел определенного размера для реализации в криптографии

  Аналитическую работу провел студент (ГУ МФТИ) кафедры радиотехники Кучин Борис.

  Источник

  Читайте также:  Врезной способ установки мойки