Простые числа

УПОРЯДОЧЕННАЯ ЖИЗНЬ

Образ жизни Рамануджана, истинного брахмана, представителя духовной касты индуистского общества, был основан на самоконтроле, умеренности и исключении из рациона питания всех животных продуктов, а также многих продуктов растительного происхождения, таких как чеснок и лук. Любопытно отметить, что на протяжении всей жизни Рамануджан записывал большинство своих математических результатов, многие из которых он не мог точно доказать, сразу после пробуждения по утрам.

* * *

Американский математик Брюс Берндт из Иллинойсского университета, посвятивший много времени изучению работ Рамануджана, обнаружил, что тот сначала составил таблицу, отличную от посланной Харди. В оригинальной таблице простые числа для первых ста миллионов натуральных чисел описаны более подробно.

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

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

Страница одной из записных книжек Рамануджана.

Глава 7 Для чего нужны простые числа

Поиск простых чисел — по крайней мере больших простых чисел — довольно сложная задача, потому что еще никому не удалось найти формулу или алгоритм, позволяющий генерировать любые простые числа. Но может возникнуть логичный вопрос: «Для чего нужно генерировать простые числа?»

На этот вопрос можно дать два ответа. Первый из них имеет теоретическое значение. Попытки генерации простых чисел ведут к появлению новых интересных инструментов для расчетов, особенно для компьютерных вычислений. Кроме того, наличие большого списка простых чисел позволяет проверять теоремы, которые еще не доказаны. Если кто-то выдвигает гипотезу относительно простых чисел, но оказывается, что одно из миллионов чисел нарушает ее, то вопрос снимается. Это стимулирует поиск простых чисел различных видов: простых чисел Мерсенна, чисел-близнецов и так далее. Иногда такой поиск превращается в соревнование, в котором устанавливаются мировые рекорды и за победы присуждаются большие призы.

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

Простые числа в криптографии

В 1975 г. Уитфилду Диффи и Мартину Хеллману, в то время работавшим в Стэнфордском университете, пришла в голову идея асимметричного шифрования, или «шифрования с открытым ключом». Эта система основана на специальных математических функциях, называемых «односторонними функциями с потайным входом», которые позволяют зашифровывать текст, но делают расшифровку практически невозможной без знания используемого кода. Идея состоит в том, что каждый пользователь имеет пару ключей: открытый и закрытый. Если мы хотим отправить кому-то сообщение, мы зашифровываем это сообщение с помощью открытого ключа — то есть ключа, известного всем. Но только человек, имеющий соответствующий закрытый ключ, может расшифровать это сообщение. Одним из преимуществ такого метода является то, что закрытый ключ никогда не передается и поэтому его не нужно постоянно менять в целях безопасности. Идея метода не совсем проста, но мы можем пояснить ее с помощью аналогии. Представьте себе большой магазин, где продаются сотни тысяч банок с краской разного цвета. Возьмем две любые банки и смешаем краску в разных количествах. Пока все просто. Теперь, если мы покажем кому-нибудь получившийся цвет и попросим «расшифровать», какое количество каких красок использовалось изначально, на такой вопрос будет очень трудно ответить.

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