Простые числа на протяжении столетий очаровывали математиков — технологии произвели революцию в их поиске

Осколок гладкой кости с нерегулярными отметками, датируемый 20 000 лет назад, озадачил археологов, пока они не заметили нечто уникальное — гравюры, линии, похожие на отметки, могли представлять простые числа . Аналогичным образом, глиняная табличка 1800 г. до н. э. с вавилонскими числами описывает систему счисления, построенную на простых числах.

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

История простых чисел

Неформально, положительное счетное число больше единицы является простым, если это количество точек может быть организовано только в прямоугольный массив с одним столбцом или одной строкой. Например, 11 является простым числом, поскольку 11 точек образуют только прямоугольные массивы размером 1 на 11 и 11 на 1. Наоборот, 12 не является простым числом, поскольку вы можете использовать 12 точек, чтобы создать массив из 3 на 4 точек с несколькими строками и несколькими столбцами. Учебники по математике определяют простое число как целое число больше единицы, единственными положительными делителями которого являются только 1 и само число.

Историк математики Питер С. Рудман предполагает, что греческие математики, вероятно, были первыми, кто понял концепцию простых чисел, около 500 г. до н. э.

Около 300 г. до н. э. греческий математик и логик Евклид доказал, что существует бесконечно много простых чисел . Евклид начал с предположения, что существует конечное количество простых чисел. Затем он придумал простое число, которого не было в первоначальном списке, чтобы создать противоречие. Поскольку фундаментальный принцип математики — быть логически последовательным без противоречий, Евклид затем пришел к выводу, что его первоначальное предположение должно быть ложным. Итак, существует бесконечно много простых чисел.

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

В средние века арабские математики развили греческую теорию простых чисел, которые в то время назывались числами хасам. Персидский математик Камаль ад-Дин аль-Фариси сформулировал фундаментальную теорему арифметики, которая гласит, что любое положительное целое число, большее единицы, может быть однозначно выражено как произведение простых чисел.

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

Простые числа можно сортировать по разным типам. В 1202 году Леонардо Фибоначчи в своей книге « Liber Abaci: Book of Calculation » ввел простые числа вида (2 ·p –1), где p также является простым числом.

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

Несколько ранних математиков считали, что число вида (2 ·p –1) является простым, когда p является простым. Но в 1536 году математик Худальрикус Региус заметил , что 11 является простым, а (2 ·11 –1) — нет. Число 2047 можно выразить как 23, умноженное на 89, что опровергает эту гипотезу.

Хотя это не всегда верно, специалисты по теории чисел поняли, что сокращение (2 p –1) часто приводит к простым числам и дает систематический способ поиска больших простых чисел.

Поиск больших простых чисел

Число (2 p –1) намного больше по сравнению со значением p и дает возможность определять большие простые числа.

Когда число (2 p –1) становится достаточно большим, становится гораздо сложнее проверить, является ли (2 p –1) простым числом, то есть можно ли расположить (2 p –1) точек только в виде прямоугольного массива с одним столбцом или одной строкой.

К счастью, Эдуард Люка разработал тест на простоту чисел в 1878 году, позже доказанный Дерриком Генри Лемером в 1930 году. Их работа привела к эффективному алгоритму оценки потенциальных простых чисел Мерсенна. Используя этот алгоритм с ручными вычислениями на бумаге, Лукас показал в 1876 году, что 39-значное число (2 127 –1) равно 170 141 183 460 469 231 731 687 303 715 884 105 727, и это значение является простым.

Также известное как M127, это число остается самым большим простым числом, проверенным ручными вычислениями. Оно удерживало рекорд самого большого известного простого числа в течение 75 лет.

Исследователи начали использовать компьютеры в 1950-х годах, и темпы открытия новых больших простых чисел увеличились. В 1952 году Рафаэль М. Робинсон определил пять новых простых чисел Мерсенна, используя стандартный западный автоматический компьютер для проведения тестов простых чисел Лукаса-Лемера.

По мере совершенствования компьютеров список простых чисел Мерсенна рос, особенно с появлением суперкомпьютера Cray в 1964 году. Хотя простых чисел бесконечно много, исследователи не уверены, сколько из них соответствуют типу (2 p –1) и являются простыми числами Мерсенна.

К началу 1980-х годов исследователи накопили достаточно данных, чтобы с уверенностью полагать, что существует бесконечно много простых чисел Мерсенна. Они даже могли предположить, как часто эти простые числа встречаются в среднем. Математики пока не нашли доказательств, но новые данные продолжают подтверждать эти догадки.

Джордж Уолтман , ученый-компьютерщик, основал Great Internet Mersenne Prime Search (GIMPS) в 1996 году. Благодаря этой совместной программе любой желающий может загрузить бесплатное программное обеспечение с веб-сайта GIMPS для поиска простых чисел Мерсенна на своих персональных компьютерах. На веб-сайте содержатся конкретные инструкции о том, как принять участие.

GIMPS уже определил 18 простых чисел Мерсенна, в основном на персональных компьютерах с использованием чипов Intel . В среднем программа делает новое открытие каждые один-два года.

Наибольшее известное простое число

Люк Дюрант , бывший программист, в октябре 2024 года обнаружил текущий рекорд самого большого известного простого числа (2 136 279 841 –1).

Это 41 024 320-значное число, обозначенное как M136279841 , было 52-м простым числом Мерсенна, которое было обнаружено с помощью GIMPS в общедоступной облачной вычислительной сети .

Эта сеть использовала чипы Nvidia и работала в 17 странах и 24 центрах обработки данных. Эти передовые чипы обеспечивают более быстрые вычисления, обрабатывая тысячи вычислений одновременно. Результатом является сокращение времени выполнения таких алгоритмов, как проверка простых чисел.

Electronic Frontier Foundation — это группа по защите гражданских свобод, которая предлагает денежные призы за определение больших простых чисел. В 2000 и 2009 годах она вручила призы за первые проверенные простые числа длиной в 1 миллион и 10 миллионов цифр .

Следующие две задачи энтузиастов больших простых чисел — определить первые 100-миллионнозначные и 1 миллиарднозначные простые числа. Призы EFF в размере 150 000 и 250 000 долларов США соответственно ждут первого успешного человека или группу.

Восемь из 10 крупнейших известных простых чисел являются простыми числами Мерсенна, поэтому GIMPS и облачные вычисления готовы сыграть важную роль в поиске рекордно больших простых чисел.

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

Предоставлено The Conversation

Источник: vk.com

Комментарии: