13.7.1 Общетеоретические обоснования

Основную часть алгоритма можно описать следующим образом. Предположим, что как-то удалось построить простое число и требуется построить еще большее простое число . Это большее число ищется в виде

(1)

Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия (1) содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии, ведь согласно условиям тестирования должно выполняться ограничение . Оценка наименьшего простого числа в арифметической прогрессии была получена еще в 1944 г. Ю. В. Линником. Она утверждает, что существует абсолютная постоянная такая, что наименьшее простое число в прогрессии (1) не превосходит . Постоянная очень велика, заведомо выполняется неравенство . В предположении расширенной гипотезы Римана о нулях L-функций Дирихле можно доказать (см. [Прах], с. 272), что при любом наименьшее простое число в прогрессии (1) не превосходит . Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа (1) с не существует. Тем не менее опыт вычислений на ЭВМ показывает, что простые числа в прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое (уже первый член прогрессии (1) есть простое число).

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

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