Зачем математики ищут простые числа с миллионами знаков?

16 Января 2018 в 10:30, Илья Хель 15 468 просмотров 24

Простые числа — это больше, чем числа, которые делятся на себя и на единицу. Это математическая загадка, которую математики пытаются разгадать с тех самых пор, когда Евклид доказал, что им нет конца. Проект Great Internet Mersenne Prime Search, перед которым стоит задача поиска большого числа простых чисел особо редкого вида, недавно открыл самое большое простое число, известное на сегодняшний день. В нем 23 249 425 цифр — это достаточно, чтобы заполнить книгу из 9000 страниц. Для сравнения: количество атомов во всей наблюдаемой Вселенной оценивается в число с не более чем сотней знаков.

Новое число, которое записывается как 2⁷⁷²³²⁹¹⁷-1 (два в 77 232 917-й степени минус один), было обнаружено волонтером, который посвятил 14 лет вычислительного времени этому поиску.


Возможно, вас удивит, зачем нам знать число, которое растягивается на 23 миллиона знаков? Ведь самые важные числа для нас — это те, которые мы используем для количественного описания нашего мира? Так, да не так. Нам нужно знать о свойствах различных чисел, чтобы не только развивать технологии, от которых мы зависим, но и сохранять их безопасность.

Безопасность простых чисел

Одно из самых распространенных применений простых чисел — система шифрования RSA. В 1978 году Рональд Ривести, Ади Шамир и Леонард Адлеман взяли за основу простейшие известные факты о числах и создали RSA. Разработанная ими система позволяла передавать информацию в зашифрованном виде — вроде номера кредитной карточке — и через Интернет.

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

Возьмем, к примеру, число 70. Оно делится на 2 и 35. Далее, 35 — произведение 5 и 7. 70 — это произведение трех меньших чисел: 2, 5 и 7. На этом все, потому что они уже не разбиваются. Мы нашли первичные компоненты, составляющие 70, осуществили его факторизацию.

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

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

Однако если Алиса выберет два больших числа, рассчитает их произведение и сообщит об этом открыто, определить первоначальные простые числа будет очень сложно, потому что только она знает факторы.

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

В поиске простых

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

Тем не менее не поиск более безопасных криптосистем и не улучшающиеся компьютеры стали причиной последнего открытия Мерсенна. Это математики одержимы поиском драгоценностей внутри сундука с надписью «простые числа». Эта жажда началась со счета «один, два, три…» и до сих пор ведет нас дальше. А то, что вместе с тем произошла революция в области Интернета, это случайность.

Известный британский математик Годфри Гарольд Харди сказал: «Чистая математика в целом значительно более полезна, чем применяется. Полезным ее делает техника, а математическая техника учится по большей части у чистой математики». Станут ли гигантские простые числа полезными, непонятно. Но поиск таких знаний утоляет интеллектуальную жажду человеческого рода, которая началась с евклидового доказательства бесконечности простых чисел.

Зачем математики ищут простые числа с миллионами знаков?

24 комментария

  1. amd212

    факторы = множители (разложение на простые множители)

  2. espro

    "Простые числа — это больше, чем числа, которые делятся на себя и на единицу"

    А разве не любое число может поделится на себя и на единицу?
    Берём к примеру 4564356, делим на 4564356 и получаем 1. 4564356:1=4564356.
    Или я что-то упускаю из описания?

  3. Elitnyy2

    Если допустить , что мир - математическая компьютерная программа , то такая эзотерическая наука как нумерология вполне может иметь под собой реальную пользу. Как пример, возьмём дату рождения 01.01.1984 Просуммируем все числа, и получим 24=2+4=6 Далее ищете в Гугле какой характер у носителя кода 6 (отправлено из приложения Hi-News.ru)

  4. Elitnyy2

    С другой стороны, математика - это абстракция, как фэнтэзи, и то, что она применима к реальному миру - лишь частичное совпадение , и, возможно , глупо ее поменять к реальной жизни. Хороший наглядный пример - любой запуск любого космического аппарата - это всегда лоторея (отправлено из приложения Hi-News.ru)

    • OneType

      Elitnyy2, Лотерея это только у рукожопых человеков. Как только они все вымрут, и уступят планету роботам, то лотерея закончится, и начнется эра гарантированных стопроцентных запусков космических аппаратов, для покорения ближнего и дальнего космоса, и заселения новых планет разумными роботами.

      • Skydreamer

        OneType, А с чего вы взяли что разумные роботы будут иметь ваше рукожопное желание заселять какие то там планеты? :-D (отправлено из приложения Hi-News.ru)

  5. Raid Ashihi

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

  6. coolwolf0

    О, давненько у нас не было корявых переводов с английского. И, традиционно, переводчик слабо понимает суть текста, не владеет предметной областью и путается в терминологии. Ну неужели в России не осталось способных математиков, которые могут грамотно изложить эту тему понятным языком? Остаётся читать блоггеров вроде sly2m в livejournal.

  7. Ce3apyc

    Дорогая редакция, признавайтесь! Илья Хель - это бот?

  8. uran

    Дайте эту задачу ии (отправлено из приложения Hi-News.ru)

Новый комментарий

Для отправки комментария вы должны авторизоваться или зарегистрироваться.