Мы все когда-то изучали простые числа, теперь любой пятиклассник (конечно, достаточно послушный, чтобы выучить уроки) объяснит вам, что это такое, приведет пару примеров и на коленях разложит небольшое число на простое факторы. Но многие пожилые люди, наверное, уже не помнят таких трюков, а почему? «Бред, опять какие-то школьные воспоминания и совершенно ненужные в жизни знания. Эти ваши простые числа я нигде, кроме школы, не употреблял», — спешу вас уверить, что они применялись не раз. Более того, они не только составляют важную часть нашей повседневной жизни, но и касаются некоторых важнейших вопросов науки, на которые до сих пор нет ответов.
Простые числа полностью оправдывают свое название – это всего лишь натуральные числа, делящиеся сами на себя и на единицу без остатка. Все остальные числа называются составными, так как строятся из простых чисел, как из «кирпичиков». Легко запомнить несколько первых простых чисел: 2, 3, 5, 7, 11, 13 и так далее (одно из них не является одним). Это не могло быть проще, не так ли? Но эти простые «математические атомы» уже давно интригуют ученых.
Представление о простых числах у людей было с древних времен, и первые попытки их анализа возникли еще в Древней Греции (да, опять же, те греки все это разыграли). Знаменитая работа Евклида «Элементы» впервые документирует одну интерпретацию принципа простых чисел, настолько важную, что ее называют «фундаментальной теоремой арифметики». Он утверждает, что любое натуральное число, большее единицы, можно простым способом разложить на простые множители. Вот вам школьная задачка — найти простые делители числа 42. Ну, конечно, сначала делим на два, получаем 21. А 21 — это трижды семь. Как мы знаем, 2, 3 и 7 — простые числа, а это значит, что ответ: 42 = 2х3х7.
Это просто только на первый взгляд, ведь число может быть больше, и оно не обязательно имеет явные делители (попробуйте сразу разложить число 221). Поиск простых чисел стал весьма популярен в эпоху Возрождения, и не имея практической ценности, это было своеобразной забавой для математиков *так они развлекались во времена без телефонов* - только теперь они начали искать числа, не являющиеся прямыми, однако использование формул не всегда эффективно.
Важным событием стала публикация формулы M=2^n – 1 (где n – простое число) французским монахом Марином Мерсенном 17 века, после чего люди бросились применять ее на практике. Эта короткая запись позволяет находить большие простые числа гораздо чаще, чем метод перебора. Например, пятое число Мерсенна (n=13) равно 2^13 – 1 = 8191. Без формулы прийти к такому результату придется долго, но это не всегда работает: число 11 тоже просто, по формуле 2^11 – 1 = 2047, и оно разлагается на 23 и 89.
Конечно, сейчас поиск чисел Мерсенна осуществляется исключительно с помощью компьютеров; с этой целью в 1996 году даже организовали целый проект «Великий интернет-поиск простых чисел Мерсенна» — крупнейший в своем роде, где волонтеры со всего мира искали самые большие простые числа. На сегодняшний день рекорд сохранился в результате расчетов 2018 года Патрика Лароша: 2^82 589 933 – 1. Это пятьдесят первое найденное число Мерсенна состоит из 82 589 933 умножений двух чисел, уменьшенных на единицу, и общая сумма составляет 24 862 048 цифр.
Здесь нужно небольшое сравнение, например, по космической хронологии с момента Большого взрыва прошло не более 10^18 секунд, это число имеет в записи 19 символов. У M(51) их около 25 тысяч, и чтобы посмотреть, как это выглядит, сначала нужно скачать десятистраничный файл с официального сайта. Чтобы доказать, что это было легко, потребовалось двенадцать дней непрерывных вычислений на машине с процессором Intel i5-4590T: Надеюсь, вам это больше не кажется примитивной школьной задачей? По традиции, авторы открытия отпраздновали свой успех откупориванием бутылки шампанского. Забавно, что некоторые люди до сих пор так проводят свое свободное время.
Как вы уже заметили, хитрость с простыми числами заключается в том, что мы можем взять определенный набор из них, умножить их и получить огромное комплексное число, но обратный процесс нахождения простых чисел (особенно если эти множители велики) или доказательства простоты невероятно трудоемкий процесс.
Обратите внимание: Почему смартфон быстро разряжается, что делать.
На этом свойстве основан наш наиболее распространенный алгоритм защиты электронных данных, RSA (названный в честь его изобретателей Ривеста, Шамира и Адлемана). Каждый раз, когда вы вводите ПИН-код карты в банкомате, вы запускаете процесс идентификации, основанный на теории простых чисел: взлом карты не является невозможным, но прямая расшифровка без специального «ключа» (который есть только у банка) потребует огромных затрат количество времени, поэтому даже пытаться, по сути, бессмысленно. Алгоритм шифрования RSA используется в качестве основы для других более сложных систем шифрования для создания уникальной цифровой подписи, и если вдруг будет найден быстрый способ ее расшифровки, нас ждет полный цифровой коллапс.Прайметал иногда находит применение в природе. Самый популярный пример — периодические цикады Северной Америки, жизненный цикл некоторых видов которых составляет 13 лет, а других — 17 лет. Конечно, столь странное совпадение вызвало интерес учёных, и сегодня существуют две гипотезы, обе основанные на свойствах простых чисел. Первый говорит о том, что такой цикл защищает их от хищников. Допустим, появляется некий хищник, питающийся цикадами, который вылупляется раз в 13 лет (а затем умирает в течение недели). Жизненный цикл самого хищника меньше, например 5 лет. Тогда следующее одновременное рождение хищников и вылупление личинок, грозящее мелким цикадам гибелью, произойдет не раньше, чем через 65 лет. Это ключевое утверждение, ведь если n — простое число (13 лет), а p (5 лет) < n, то их наименьшее общее кратное равно их произведению — np (13x5=65).
Второй момент: такой жизненный цикл позволяет «упустить» не только хищников, но и их сородичей, имеющих другую длину жизненного цикла. Первое совпадение вылупления у двух видов цикад произойдет только через 13х17 лет, т е через 221 год (ответ на вопрос из пункта 4). Возможно, если бы одновременно появились разные виды цикад, это привело бы к скрещиванию и появлению потомства с нерегулярным циклом.
Простые числа изучаются уже очень давно, но вы, возможно, удивитесь, узнав, что у нас до сих пор нет волшебной формулы, позволяющей предсказать, где они находятся на числовой прямой. Давай сделаем это снова. Если нам даны числа от единицы до бесконечности, мы не знаем, как точно вычислить простые числа среди них. Ученые придумали всякие штуки, чтобы хоть как-то формализовать их расположение: создается ощущение, что они появляются совершенно спонтанно, без какой-либо закономерности. С другой стороны, именно это позволяет нам безопасно использовать шифрование RSA, поэтому проблема невелика, но у нас есть и другие непроверенные гипотезы в этой области, такие как гипотеза Гольдбаха. Он гласит, что любое четное число, начиная с 4, можно представить в виде суммы двух простых чисел. Например, 8=3+5; 24=13+11 и так далее. Выглядит не страшно, но доказательства гипотезы до сих пор нет: проверены уже сотни четных чисел, и все они удовлетворяют условию, но для математиков это пустые слова. Достаточно одного исключения из правил, чтобы гипотеза оказалась ложной.
Однако, пожалуй, самой интригующей, известной и сложной проблемой является гипотеза Римана о распределении простых чисел (которую я не могу здесь точно описать, но не могу не рассказать о ней, так что просто вникните в суть вопроса) ее важность) — одна из семи проблем тысячелетия, семи математических задач, выявленных Математическим институтом Клея в 2000 году, за решение каждой из которых предусмотрено вознаграждение в 1 миллион долларов. Ей посвящены трактаты и книги, о ней бьются уже целых 160 лет (!), но она до сих пор остается в «неразгаданном» статусе. Говорят, что Дэвид Гильберт (лидер математического сообщества начала 20-го века) однажды сказал, что, если бы он заснул на тысячу лет, первое, что он спросил бы, когда проснулся, — была ли уже доказана гипотеза Римана.
В общем, нас с детства обманывают: простые числа, оказывается, вовсе не простые числа, и настолько, что защищают наши банковские данные от мошенников, маленьких цикад от нападений хищников, и в то же время водят ужасно сумасшедшие математики.
Эта "нашивка на коленке" делалась специально для конкурса, но если дело вдруг не удастся, можно будет добавить несколько слов позже, ведь по закону сохранения энергии: произведение, использованное автором, должно быть равно количеству теплоты реакции на питатели.
PS Меня забавляет тот факт, что Риман, который никогда не писал никаких работ на эту тему (он занимался чем-то другим), просто пришел, посмотрел на эту суматоху, а потом бросил свою злосчастную восьмистраничную гипотезу и. исчез. Обмен на комментарии серьезных ребят, лол. Обожаю математику :3
Подпишитесь, чтобы не пропустить новые интересные публикации!
Автор статьи - Александр Грибоедов
Больше интересных статей здесь: Новости науки и техники.
Источник статьи: «В школе вас обманывали!» - Или почему простые числа не так просты?.