5. Алгоритм, доказывающий непростоту числа

1. Выберем случайным образом число и проверим для этого числа указанные выше свойства а) и

2. Если хотя бы одно из них нарушается, то число N составное.

3. Если выполнены оба условия а) и возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей 1. А вероятность не определить его после к повторений не превосходит т. е. убывает очень быстро.

Миллер предложил детерминированный алгоритм определения составных чисел, имеющий сложность однако справедливость его результата зависит от недоказанной в настоящее время расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия а) и (3) для всех целых чисел Если при каком-нибудь а из указанного промежутка нарушается одно из условий а) или число N составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется.

Напомним некоторые понятия, см. [4], необходимые для формулировки расширенной гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть целое число. Функция называется характером Дирихле по модулю или просто характером, если эта функция периодична с периодом отлична от нуля только на числах, взаимно простых с и мультипликативна, т. е. для любых целых выполняется равенство Для каждого существует ровно характеров Дирихле. Они образуют группу по умножению. Единичным элементом этой группы является так называемый главный характер равный 1 на всех числах, взаимно простых с и 0 на остальных целых числах. Порядком характера называется его порядок как элемента мультипликативной группы характеров.

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

В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа существует квадратичный невычет а, удовлетворяющий неравенствам Константа 70 была сосчитана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого

невычета без использования расширенной гипотезы Римана, но с худшей оценкой 2 а справедливой при любом положительном ей большем некоторой границы, зависящей от

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