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