Проверка чисел на простоту

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

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

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

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

Решето Эратосфена. Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

• 1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
• 2. Пусть переменная p изначально равна двум — первому простому числу. Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …).
• 3. Найти первое не зачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
• 4. Повторять шаги 3 и 4, пока возможно. Теперь все не зачёркнутые числа в списке — простые.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа, потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .

Тест на основе малой теоремы Ферма. На основании этой теоремы можно построить вероятностный алгоритм проверки на простоту числа. Если для некоторого целого из интервала соотношение не выполняется, то число — составное. Если же теорема выполняется, то вывод, что число простое, сделать нельзя, так как теорема дает лишь необходимое условие. Поэтому, если для некоторого имеет место соотношение, то говорят, что число является псевдопростым по основанию. Существует бесконечно много пар чисел и, где — составное и псевдопростое. Вообще для любого существуют бесконечно много псевдопростых чисел по основанию .

Определение. Составные числа, для которых при всех основаниях выполняется сравнение, называются числами Кармайкла.

Схема данного алгоритма выглядит следующим образом:

Дано число и параметр = 1 для идентификации результата проверки.

• 1) делается случайный выбор целого числа из интервала
• 2) используя алгоритм Евклида, вычисляется НОД для чисел и
• 3) если НОД больше 1, то выполняется шаг 7
• 4) для числа проверяется сравнение
• 5) если сравнение не выполняется, то определяется параметр (число составное) переход на шаг 7.
• 6) если сравнение выполнено, то можно повторить тест;
• 7) выдать результат проверки (- число составное). При завершении работы алгоритма возможны следующие выводы:
  • · число n — составное ()
  • · если, то число является либо простым, либо составным и числом Кармайкла.