Доказательство бинарной проблемы Гольдбаха для чисел высокого порядка

Бредихин Арсентий Игоревич – магистрант Югорского государственного университета.

Аннотация: В данной статье описывается доказательство бинарной проблемы Гольдбаха для двух произвольных промежутков натуральных четных чисел высокого порядка (~1018) методом полного перебора. Здесь обосновывается выбор данных промежутков, описывается алгоритм определения простоты числа и его последующая модификация с целью повышения его быстродействия. Также представлены результаты перебора чисел из данных 2 промежутков данным алгоритмом и полученные практические результаты.

Ключевые слова: Теория чисел, простые числа, четные числа, бинарная проблема Гольдбаха, алгоритмы, перебор, программа.

Введение

В 1742 г. Гольдбах в письме к Эйлеру поставил проблему доказать, что каждое нечетное число может быть представлено в виде суммы трех простых чисел (начиная с 7). Эйлер в ответном письме высказал гипотезу, что имеет место гораздо более сильное утверждение, которое гласит, что каждое четное число, начиная с 4, может быть представлено в виде суммы двух простых чисел. Эти проблемы получили название проблемы Гольдбаха-Эйлера [1, с. 360]. Последняя из этих проблем носит название бинарной гипотезы Гольдбаха.

Бинарная проблема Гольдбаха относится к проблемам аддитивной теории простых чисел, т.е. теории простых чисел, рассматривающей их в качестве слагаемых [1, с. 360]. За 276 лет ее существования данная проблема так и не была решена для всех четных чисел. Однако до сих пор предпринимаются попытки ее доказательства, но не для всех четных чисел, а для некоторых конечных промежутков четных чисел. Краткая история доказательств бинарной проблемы Гольдбаха представлена в таблице 1.

Таблица 1. История доказательств бинарной проблемы Гольдбаха [2].

Верхняя граница

Авторы доказательства

goldbah_1__html_f38e0315 (10 тыс.)

Desboves 1885

goldbah_1__html_861364c9 (100 тыс.)

Pipping 1938

goldbah_1__html_f6da570c (100 млн.)

Stein and Stein 1965ab

goldbah_1__html_fee0564c (20 млрд.)

Granville et al. 1989

goldbah_1__html_e500fb5a (400 млрд.)

Sinisalo 1993

goldbah_1__html_9dabb777 (100 трлн.)

Deshouillers et al. 1998

goldbah_1__html_a42f1565 (400 трлн.)

Richstein 1999, 2001

goldbah_1__html_10c40f9b (20 квадрлн.)

Oliveira e Silva (Mar. 24, 2003)

goldbah_1__html_2d64ef47 (60 квадрлн.)

Oliveira e Silva (Oct. 3, 2003)

goldbah_1__html_d072971d (200 квадрлн.)

Oliveira e Silva (Feb. 5, 2005)

goldbah_1__html_4df76ccd (300 квадрлн.)

Oliveira e Silva (Dec. 30, 2005)

goldbah_1__html_3845236a (1,2 квинтлн.)

Oliveira e Silva (Jul. 14, 2008)

goldbah_1__html_a316a08a (4 квинтлн.)

Oliveira e Silva (Apr. 2012)

Как видно из таблицы 1, верхняя граница на́чала резко возрастать, начиная с 60-х годов XX века. Основным толчком к этому послужило, как нетрудно догадаться, появление и развитие вычислительной техники.

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

Выбор промежутков и метода доказательства

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

Следовательно, для определения соответствия четного числа бинарной проблеме Гольдбаха необходимо использовать алгоритм определения простоты числа.

В данной работе были произвольно выбраны следующие 2 промежутка для доказательства: goldbah_1__html_bc0ccf1c (50001 четное число) и goldbah_1__html_79684847 (250001 четное число).

Алгоритм определения простоты числа

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

Теорема. Натуральное число m является простым, если для него не существует целых множителей в промежутке goldbah_1__html_d284eaa.

Доказательство. При доказательстве данной теоремы будем оперировать понятием «среднее геометрическое», которое определяется как корень степени n из произведения n чисел. В данном случае мы рассмотрим натуральное число m такое, что goldbah_1__html_89bb43b.

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

Любое число можно представить в виде произведения не менее 2 множителей. Обобщая вышесказанное, получаем, что для числа m такого, что goldbah_1__html_72fd6837, наибольшее значение будет принимать среднее геометрическое 2 чисел, поскольку оно определяется как корень степени 2 числа m.

Согласно свойству среднего геометрического нескольких чисел, оно всегда больше или равно минимальному числу и всегда меньше или равно максимальному числу. В таком случае как минимум один из множителей числа m меньше или равен среднему геометрическому числа m. Поэтому для определения простоты числа m достаточно рассмотреть его делимость на натуральные числа со значением не больше goldbah_1__html_750e8add, начиная с 2 (промежуток goldbah_1__html_d284eaa). Число 1 в промежуток не включаем, поскольку оно по определению не является простым (любое простое число имеет значение не менее 2).

Простое число m, согласно определению, делится только на 1 и само на себя (т.е. m). Эти числа в промежуток goldbah_1__html_d284eaa не входят. Следовательно, теорема доказана.

Таким образом, реализованный алгоритм определения простоты числа m сводится к простому перебору всех целых чисел из промежутка goldbah_1__html_d284eaa и проверке делимости числа m на эти числа. Если на этом промежутке находится хотя бы один делитель числа m, то алгоритм завершает свою работу на первом же делителе и число m является составным; если же таких делителей нет, то число m – простое.

Но данный алгоритм имеет недостаток – невысокая скорость работы для больших чисел (начиная с чисел порядка goldbah_1__html_2c330c35). А в рамках доказательства необходимо рассмотреть числа порядка goldbah_1__html_ea2f7d69.

Лемма. Если число goldbah_1__html_39869698 нацело делится на goldbah_1__html_340ababa и число m простое, то число a нацело делится на m.

Доказательство. Рассмотрим число goldbah_1__html_43b17da2. Поскольку число a нацело делится на goldbah_1__html_d9ad2679 и goldbah_1__html_39869698, то goldbah_1__html_2a140ab1. Разделим число a на m:

goldbah_1__html_80e9f410. (1)

Поскольку goldbah_1__html_a35e76db, то и goldbah_1__html_95df9253. Следовательно, goldbah_1__html_23b0d67b, что и требовалось доказать.

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

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

Реализация программы доказательства бинарной гипотезы Гольдбаха

С помощью алгоритма определения простоты числа m, принцип которого заключается в переборе всех целых чисел из промежутка goldbah_1__html_d284eaa и проверке делимости числа m на эти числа, был составлен словарь простых чисел от 2 до goldbah_1__html_53e65d80 (250 тыс.), который позволяет проверять на простоту числа до goldbah_1__html_d153eee8 (62,5 млрд.).

Но данный словарь простых чисел не устраивает автора статьи – ведь требуется проверить числа до goldbah_1__html_95b59979 Поэтому с помощью первого словаря простых чисел был составлен второй словарь простых чисел от 2 до goldbah_1__html_42247b08 (3 млрд.). Он позволяет проверять на простоту числа доgoldbah_1__html_c66e6d52 (9 квинтлн.). Поскольку goldbah_1__html_cd8a8405, то данного словаря простых чисел вполне хватает для проверки чисел такого порядка на простоту. Процесс составления словаря простых чисел занял около 6 дней на обычном ПК (персональном компьютере).

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

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

Затем модернизированный алгоритм определения простоты числа и использующая этот алгоритм программа доказательства бинарной гипотезы Гольдбаха была реализована на языке программирования Python 3.5, в среде программирования Spyder.

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

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

Результаты перебора чисел

Реализованная ранее программа доказательства бинарной гипотезы Гольдбаха была выполнена на высокопроизводительном сервере. Рассмотрим ее результаты.

Результаты выполнения программы для четных чисел из промежутка goldbah_1__html_bc0ccf1c:

goldbah_1__html_64314db1

Рисунок 1. Результаты выполнения программы.

Замечание. Число справа от пометки «Да» обозначает количество четных чисел, соответствующих бинарной гипотезе Гольдбаха, а число справа от пометки «Нет» – количество четных чисел, не соответствующих бинарной гипотезе Гольдбаха.

Количество чисел, не соответствующих бинарной гипотезе Гольдбаха, равно 0 (нет таких чисел). Это значит, что все четные числа данного промежутка соответствуют бинарной гипотезе Гольдбаха, т.е. любое четное число из данного промежутка можно представить в виде суммы двух простых чисел.

Из рисунка 1 можно увидеть, что размер словаря простых чисел от 2 до goldbah_1__html_42247b08 (3 млрд.) составляет около 144,45 миллиона простых чисел. Это означает то, что использование модернизированного алгоритма определения простых чисел для проверки на простоту чисел до goldbah_1__html_5af5de2 (9 квинтлн.) по сравнению с обычным алгоритмом определения простых чисел дает увеличение производительности алгоритма до

goldbah_1__html_442a4e07

раз.

Время выполнения программы составило около 8 дней. Объем используемой оперативной памяти во время работы программы составлял около 8 Гб.

Результаты выполнения программы для четных чисел из промежутка goldbah_1__html_79684847:

goldbah_1__html_fda4ae15

Рисунок 2. Результаты выполнения программы.

Количество чисел, не соответствующих бинарной гипотезе Гольдбаха, и в этом случае равно 0. Это значит, что все четные числа данного промежутка соответствуют бинарной гипотезе Гольдбаха, т.е. любое четное число из данного промежутка можно представить в виде суммы двух простых чисел.

Время выполнения программы составило около 45 дней. Объем используемой оперативной памяти во время работы программы был таким же – около 8 Гб.

Таким образом, бинарная гипотеза Гольдбаха оказалась справедлива для следующих двух промежутков натуральных чисел: goldbah_1__html_bc0ccf1c и goldbah_1__html_79684847.

Заключение

В результате выполнения данной работы была доказана бинарная гипотеза Гольдбаха для двух произвольных промежутков натуральных чисел: goldbah_1__html_bc0ccf1c и goldbah_1__html_79684847.

Вместе с тем получены практические результаты в виде списков простых чисел высокого порядка. Так, получены 2051 простое число в промежутке goldbah_1__html_f0a177d7 и 11599 простых чисел в промежутке goldbah_1__html_79684847. Данные простые числа можно использовать, например, в алгоритмах криптографии (в частности, алгоритм RSA [3, с. 77], который использует для генерации ключей как раз простые числа) для шифрования и дешифрования информации. Получаемые с помощью данных простых чисел ключи будут достаточно надежными, что позволит обеспечить высокую стойкость систем шифрования к взломам.

Благодарности:

Автор статьи выражает благодарность директору УПЦИТ ЮГУ и преподавателю ИТСИТ ЮГУ Карпову Дмитрию Викторовичу за предоставленный доступ к серверу в целях проведения работы по доказательству бинарной гипотезы Гольдбаха.

Список литературы

  1. Бухштаб А.А. Теория чисел. Издательство «Просвещение», Москва, 1966. 384 с.
  2. Goldbach Conjecture – from Wolfram MathWorld. – [Электронный ресурс] – Режим доступа. – URL: http://mathworld.wolfram.com/GoldbachConjecture.html (дата обращения: 08.10.2018 г.).
  3. Ожиганов А.А. Криптография: учебное пособие. – СПб: Университет ИТМО, 2016. – 140 с.