ТЕОРИЯ ЧИСЕЛ: ПРОСТЫЕ ЧИСЛА И УНИВЕРСАЛЬНОЕ УРАВНЕНИЕ

        А.М. Белов

    Для описания самых сложных и трудно поддающихся описанию формулами процессов и объектов может применяться универсальное уравнение:

    где [ ] - (и далее по тексту) математический знак обозначающий целую часть числа.

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

    Учитывая широкие возможности универсального уравнения можно ожидать, что  его применение позволит продвинуться в вопросе представления одной формулой последовательности простых чисел. Поскольку этот вопрос является весьма сложным ниже рассмотрены лишь возможные подходы к описанию последовательности простых чисел формулой, составленной на основе использования универсального уравнения.

     Самым простым и очевидным способом использования универсального уравнения при описании последовательности простых чисел является непосредственное задание этим уравнением последовательности простых чисел на основе таблицы известных простых чисел путем замены x¡ на порядковый номер n простого числа в последовательности простых чисел, а y¡ на значение этого простого числа:

    y=[n]·[1/n]·2 + [n/2]·[2/n]·3 + [n/3]·[3/n]·5 + [n/4]·[4/n]·7 + [n/5]·[5/n]·11 + [n/6]·[6/n]·13 +[n/7]·[7/n]·17+...

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

    При использовании универсального уравнения совместно с малой теоремой Ферма  для задания числового ряда:

0 +  2 +  3 +  0 +  5 +  0 +  7 +  0 +  0 +  0 +  11 +  0 +  13 +  0 +  0 +  0 +  17 +  0 +  19 +  0 +  0 +  0 +  23 +  0 +  0 +  0 +  0 +  0 +  29 +  0 +  31 +  0 +  0 +  0 +  0 +  0 +  37 +  0 +  0 +  0 +  41 +  0 +  43 +  0 +  0 +  0 +  47 +  0 +  0 +  0 +  0 +  0 +  53 +  0 +  0 +  0 +  0 +  0 +  59 +  0 +  61 +  0 +  0 +  0 +  0 +  0 +  67 +  0 +  0 +  0 +  71 +...,

в котором все члены не равные простым числам равны нулю можно получить формулу существенно меньшего объема:

    Нетрудно заметить, что в этой формуле с ростом n слишком быстро будут расти объемы вычислений и используемые при вычислениях по формуле числа.

    Рост объема вычислений с увеличением n при формировании ряда можно несколько замедлить если при составлении формулы для вычисления членов ряда совместно с универсальным уравнением использовать тест простоты числа n заключающийся в проверке его на делимость на все простые числа меньшие, чем корень из n. При этом формула, задающая числовой ряд увеличится в объеме и будет иметь следующий вид:

    P - порядковый номер выбранного предельного члена ряда. В этой формуле применение универсального уравнения обеспечило изменение верхнего предела произведения в ходе выполнения вычислений. 

    Для того, что бы посмотреть, как работает формула на форме в Visual Basic создайте кнопку и загрузите в нее следующий код, имитирующий использование формулы:  

    Изменяя в представленном коде значение P будете получать  значение ряда и частичную сумму ряда для N  от 0 до P. Причем представленный код полностью имитирует вычисления по формуле в ручную.

    Представленный код не содержит операторов управления порядком выполнения команд. Таких, например, как If … Then. Что характерно при выполнении вычисления по формуле и не характерно при выполнении вычислений по алгоритму.

    Демонстрационную версию программы можно посмотреть на http://stob2.narod.ru/program/prost.htm.

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

    Для того, что бы посмотреть, как работает формула на форме в Visual Basic создайте кнопку и загрузите в нее следующий код, имитирующий использование формулы: 

    Представленный код не содержит операторов управления порядком выполнения команд. Таких, например, как If … Then. Что характерно при выполнении вычисления по формуле и не характерно при выполнении вычислений по алгоритму. Это доказывает, что рассматриваемое выражение действительно является математической формулой (уравнением), а не просто записанным особым образом алгоритмом.

    Демонстрационную версию программы можно посмотреть на http://stob2.narod.ru/program/prost.htm.

    При изменении в представленном коде значения P в результате вычислений по программе будет получаться новое простое число W  большее P. Например, при подстановке значений Р в интервале от 641 до 647 по формуле можно вычислить ряд простых чисел, приведенных в таблице:

    Числа 641, 643, 647 являются простыми. Как видно из таблицы формула позволяет вычислить новые простые числа только для Р тоже простых.

    Необходимо учитывать, что сумма S всех простых чисел ряда от 1 до Р тем больше отличается от вычисленного W, чем больше Р и соответственно W. Исходя из этого для уменьшения объема вычислений в формулу можно ввести поправочные коэффициенты, зависящие от величины P и W.

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

   При изменении в представленном коде рассматриваемой формулы значения P в результате вычислений по программе будет получаться новое простое число W большее P. Например, при P = 2 W = 3, при P = 20 W = 79, при P = 201 W = 4229, при P = 199991 W = 1709400841, при P = 199999 W = 1709600813, при P = 200000 W = 1709600813.

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

   Очевидно, что если в формулу последовательно подставлять числа натурального ряда 2, 3, 4, 5, 6, 7,…, то ряд натуральных чисел будет преобразован в бесконечный ряд, состоящий только из простых чисел. Фрагмент такого ряда приведен в следующей таблице:

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

   Кроме этого, так как формула позволяет вычислить новые простые числа только для Р тоже простых, то ее можно использовать для тестирования абсолютно всех чисел на простоту. Поскольку очевидно, что если при помощи формулы для некоторого числа Р вычислить значение W₁, а затем вычислить значение W₂ для числа Р-1 и если в результате окажется, что W₁ = W₂, то число Р является составным, а если W₁ будет отличаться от W₂, то число Р будет являться простым.

   Так, например, для числа Р = 75353 W₁ = 264480091, а для числа Р – 1 = 75353 – 1 = 75352 W₂ = 264404731. Так как W₁ и W₂ отличаются друг от друга, то исходя, из выше приведенных рассуждений, число 75353 будет являться простым числом.

   Для числа Р = 75367 W₁ = 264555491, а для числа Р – 1 = 75367 – 1 = 75366 W₂ = 264480091. Так как W₁ и W₂ отличаются друг от друга, то исходя, из выше приведенных рассуждений, число 75367 так же будет являться простым числом.

   А вот для числа Р = 75361 W₁ = 264480091, и для числа Р – 1 = 75361 – 1 = 75360 W₂ = 264480091. Так как W₁ = W₂, то исходя, из выше приведенных рассуждений, число 75361 будет являться составным числом.

   Действительно число 75361 можно разложить на следующие простые множители: 75361 = 11 · 13 · 17 · 31.

   Более того, так как значение W изменяется только при достижении числа 75367, то можно утверждать, что между простыми числами 75353 и 75367 будут располагаться только составные числа.

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

   Вообще-то на фоне представлений о непредсказуемости, хаотичности и случайности появления простых чисел в ряду натуральных чисел само существование представленных в данной статье формул выглядит довольно странным. Проще говоря, этих формул не должно было бы быть. Но они существуют…

   В этой связи необходимо отметить, что о существовании статистической закономерности в распределении среди натуральных чисел простых чисел известно уже сравнительно давно. Еще в 1792-1793 годах Гаусс эмпирическим путем обнаружил, что число простых чисел на отрезке от единицы до некоторого числа в среднем близко к величине обратно пропорциональной его логарифму. В дальнейшем для изучения закономерности распределения простых чисел оформился специальный раздел теории чисел. Правда все исследования в рамках этого раздела фактически свелись либо к уточнению вида функции распределения простых чисел, либо к обоснованию существования этой функции в различных ее представлениях.

   Однако немецкий математик Бернхард Риман смог обнаружить, что функция распределения простых чисел – количество простых чисел, не превосходящих некоторое заданное число, выражается через распределение так называемых нетривиальных нулей дзета-функции. И сформулировал гипотезу: «Все нетривиальные нули дзета-функции имеют действительную часть, равную 1/2», то есть являются комплексными числами, расположенными на прямой х=1/2, проходящей сквозь дзета-функцию.

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

   Правда, несмотря на то, что свою гипотезу Риман сформулировал еще в 1859 году, доказать ее пока не удалось. С другой стороны существование рассматриваемых формул ведь можно рассматривать в качестве косвенного доказательства гипотезы Римана.

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

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

                                                                                                            март 2003 года
Выход на главную страницу http://stob2.narod.ru