Разгадка тайны простых чисел угрожает современной криптографии
Двое математиков утверждают, что сделали шаг вперед к пониманию простых чисел и к доказательству гипотезы Римана, одной из самых увлекательных загадок математики, передает BBC News. Ден Голдстон из университета штата Сан-Хосе и Чем Ялдирим из университета Богазичи в Стамбуле доложили о результатах своей работы на конференции, посвященной теориям алгоритмов, в Германии.
Некоторые ученые считают, что работа Голдстона и Ялдирима является одной из самых ярких в области математики за последние несколько десятилетий.
Гипотеза Римана о распределении ряда простых чисел была сформулирована в 1859 году. Простое число - целое положительное число, большее единицы, делящееся только на единицу и само себя (2, 3, 5, 7, 11, 13 и так далее). Среди простых чисел встречаются так называемые "близнецы" или пары простых чисел, разница между которыми составляет двойку (например, 11 и 13). "Близнецы" появляются с некой периодичностью, причем, чем больше числа, тем реже они встречаются (11 и 13; 17 и 19; 29 и 31; 41 и 43; 59 и 61). То же происходит и с обычными простыми числами. В числах, близких к триллиону, лишь каждое 28 число является простым.
Простые числа занимали древних математиков еще 2 тысячи лет назад. Эратосфен первый построил алгоритм нахождения простых чисел - так называемое "решето Эратосфена". Евклид доказал, что простых чисел бесконечно много. Однако окончательного ответа на вопрос, конечно или бесконечно множество "близнецов", пока не существует. Распределение простых чисел среди всех натуральных чисел не подчиняется никакой закономерности, однако немецкий математик Бернгард Риман (1826 - 1866), введя понятие так называемой дзеты-функции, утверждал, что ряд этих "близнецов" бесконечен.
Голдстон подошел к решению задачи немного с другой стороны, попытавшись сначала ответить на вопрос: возможно ли найти пару простых чисел, которые не были бы "близнецами", но располагались ближе друг к другу, чем обычные простые числа. После многих лет совместной работы ученые смогли доказать, что такие числа существуют.
Математики считают, что работа ученых имеет огромное значение для решения задачи определения периодичности возникновения простых чисел и чисел "близнецов". Доказательство гипотезы Римана может иметь практическое применение гораздо шире, чем кажется на первый взгляд. Простые и так называемые "полупростые" числа (которые делятся только на два других простых числа) - лежат в основе системы криптографии, известной как RSA. Поэтому если гипотеза будет доказана, то это приведет к революционному прорыву в области криптографии.
В 2000 году математический институт Клея назначил премию в миллион долларов тому, кто докажет теорему Римана или опровергнет ее. Голдстон надеется, что он со своим коллегой продвигаются в правильном направлении.
Комментарий
Как это ни парадоксально, но "лучшее понимание" простых чисел может грозить катастрофой современной криптографии, а вовсе не "новыми успехами". Дело в том, что в основе современных способов кодирования лежит своеобразное "бессилие" математики: алгоритмы, позволяющие разложить большое число на простые сомножители, требуют такой напряженной работы компьютеров, что за это время передаваемая информация успеет потерять актуальность, поэтому системы "открытых ключей" и считаются безопасными. И не надо думать, что при крушении RSA пострадают только разведчики и параноидально настроенные граждане; подобные алгоритмы, например, позволяют производить безопасные платежные транзакции в сети...
Ссылки:
Введение в криптографию - под ред. В.В.Ященко
Цифровая подпись. Эллиптические кривые. Шифрование