Математик который нашел способ поиска простых чисел

Простые числа: история и факты

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 — 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.

У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.

Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.

Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2 n -1 является простым, то число 2 n-1 * (2 n -1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.

В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».

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

Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2 n -2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2 341 — 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2 n +1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 2 32 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Числа вида 2 n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.

Но не все числа вида 2 n — 1, где n – простое, являются простыми. К примеру, 2 11 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.

Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M₁₉, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M₃₁ также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M₁₂₇ — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃ и M₂₂₈₁.

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M_25964951, состоит из 7816230 цифр.

Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 2 32 +1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.

Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.

На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как

π(n) = n/(log(n) — 1.08366)

А Гаусс – как логарифмический интеграл

с промежутком интегрирования от 2 до n.

Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.

В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:

• гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
• гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
• бесконечно ли количество простых чисел вида n 2 + 1 ?
• всегда ли можно найти простое число между n 2 and (n + 1) 2 ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
• бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
• существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26.
• бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
• n 2 — n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n 2 — 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
• бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
• бесконечно ли количество простых чисел вида n# -1 ?
• бесконечно ли количество простых чисел вида n! + 1?
• бесконечно ли количество простых чисел вида n! – 1?
• если p – простое, всегда ли 2 p -1 не содержит среди множителей квадратов простых чисел
• содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

Текущие рекорды среди простых чисел

Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта.
www.mersenne.org/primes

Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

Источник

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.

В виде алгоритма решето Эратосфена формализуется следующим образом:

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

После выполнения этой операции незачёркнутыми в списке остаются только простые числа.

Очевидно, что компьютерная реализация решета Эратосфена требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил 38-летний перуанский математик Харальд Хельфготт.

Харальд Хельфготт

Харальд Хельфготт привлёк всеобщее внимание в 2013 году, когда ему удалось решить тернарную проблему Гольдбаха. Тернарная проблема Гольдбаха — более слабое утверждение основной бинарной проблемы Гольдбаха — одной из самых известных открытых математических проблем, которая до сих пор остаётся нерешённой. Это утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.

Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от N до бесконечности Иваном Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что нижняя граница N в работе Виноградова составляет 10 6 846 168 .

Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу, снизив границу N до приемлемого числа 10 29 , а все остальные числа проверили на суперкомпьютере. Его доказательство опубликовано в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао.

Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки — оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена — метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется.

«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.

Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.

Специалисты говорят, что эффективность алгоритма определяется двумя факторами:

1. Количество операций на один бит входных данных.
2. Количество бит в памяти во время выполнения инструкций.

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

Оптимизация решета Эратосфена

Для оптимизации компьютерного алгоритма решета Эратосфена математик применил вариант того же метода, который использовал при работе над тернарной проблемой Гольдбаха. Речь идёт о круговом методе Харди-Литтлвуда. Том самом методе, который в начале прошлого века великолепно усовершенствовал математик Иван Виноградов, в результате чего почти сумел доказать гипотезу Гольдбаха.

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

Сам математик объясняет метод следующим образом:

«Анализ количества решений производится, по сути, посредством преобразования Фурье. Представьте себе, что простые числа — это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, — это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, — это малые дуги. Весь метод распадается на две части — выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй — на малые».

На основе метода Харди-Литтлвуда учёный разработал подход, который позволяет вместо объёма оперативной памяти N использовать объём памяти ∛N (кубический корень из N).

Образно говоря, вместо 1 гигабайта памяти, т.е. 10 9 байт (не путать с гибибайтом 2 30 ) нужен всего лишь 1 килобайт (∛10 9 = 10 3 байт).

Гигабайт и килобайт — большая разница, согласитесь.

Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.

Тезисы своей работы Харальд Хельфготт представил на 21-м Латиноамериканском коллоквиуме по алгебре в Буэнос-Айресе 25-29 июля 2016 года, а также на мероприятии Sinapsis 2016 в Париже — неформальной встрече перуанских учёных, проживающих в Европе.

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

Источник