Простые числа — это больше, чем числа, которые делятся на себя и на единицу. Это математическая загадка, которую математики пытаются разгадать с тех самых пор, когда Евклид доказал, что им нет конца. Проект 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 использует это преимущество.
Допустим, Алиса и Боб хотят секретно пообщаться в Интернете. Им нужна система шифрования. Если они сначала встретятся лично, они могут оговорить метод шифрования и дешифрования, который будет известен только им, но если же первый разговор состоится в онлайне, им придется сперва открыто обсудить систему шифрования — а это риск.
Однако если Алиса выберет два больших числа, рассчитает их произведение и сообщит об этом открыто, определить первоначальные простые числа будет очень сложно, потому что только она знает факторы.
Поэтому Алиса сообщает свое произведение Бобу, сохраняя в тайне факторы. Боб использует произведение для шифрования своего послания Алисе, которое можно расшифровать только при помощи известных ей факторов. Если Ева захочет подслушать, она никогда не сможет расшифровать сообщение Боба, если не заполучит факторы Алисы, а Алиса, конечно, будет против. Если Ева попытается разложить произведение — даже при помощи самого быстрого суперкомпьютера — у нее это не получится. Просто не существует такого алгоритма, который справился бы с этой задачей за время жизни Вселенной.
В поиске простых
Большие простые числа также используются в других криптосистемах. Чем быстрее компьютеры, тем больше числа, которые они могут взломать. Для современных приложений достаточно простых чисел, содержащих сотни цифр. Эти числа незначительны по сравнению с недавно обнаруженным гигантом. На самом деле новое простое число настолько большое, что в настоящее время ни один возможный технологический прогресс в скорости вычислений не может привести к необходимости использовать его для криптографической безопасности. Вполне вероятно, что даже риски, обусловленные появлением квантовых компьютеров, не потребуют использования таких монстров для безопасности.
Тем не менее не поиск более безопасных криптосистем и не улучшающиеся компьютеры стали причиной последнего открытия Мерсенна. Это математики одержимы поиском драгоценностей внутри сундука с надписью «простые числа». Эта жажда началась со счета «один, два, три…» и до сих пор ведет нас дальше. А то, что вместе с тем произошла революция в области Интернета, это случайность.
Известный британский математик Годфри Гарольд Харди сказал: «Чистая математика в целом значительно более полезна, чем применяется. Полезным ее делает техника, а математическая техника учится по большей части у чистой математики». Станут ли гигантские простые числа полезными, непонятно. Но поиск таких знаний утоляет интеллектуальную жажду человеческого рода, которая началась с евклидового доказательства бесконечности простых чисел.