Производители компьютеров и интернет-провайдеры пытаются снизить этот риск, предлагая пользователям различные системы шифрования. Надо сказать, что внедрение компьютеров изменило как саму криптографию, так и криптоанализ — искусство взлома шифров. В настоящее время разработано множество новых шифров. Один из самых известных шифров, который в 1978 г. придумали Рональд Ривест, Ади Шамир и Леонард Адлеман, основан на использовании простых чисел. Больших простых чисел, примерно 100-значных. Система Ривеста — Шамира — Адлемана (известная как RSA) используется во многих компьютерных операционных системах, встроена в основные протоколы безопасного интернет-соединения, ею широко пользуются правительства, корпорации и университеты. Конечно, не каждое новое открытие, имеющее отношение к простым числам, может повлиять на безопасность вашего банковского счета, но это добавляет теме интереса. Как только удается выяснить что-то новое, что помогает связать простые числа и компьютерные вычисления, это привлекает повышенное внимание. Так случилось и с тестом Агравала — Каяла — Саксены, хотя при всей своей математической элегантности и важности непосредственного практического значения он не имеет.

Тем не менее он позволил немного под другим углом рассмотреть общий вопрос криптографии по Ривесту — Шамиру — Адлеману, и результат вызывает некоторые опасения. До сих пор не существует ни одного алгоритма P-класса для решения второй из названных Гауссом задач — разложения на простые множители. Большинство специалистов сходятся во мнении, что такого алгоритма не существует, но в последнее время их уверенность несколько поколебалась. Поскольку где-то за кулисами, совсем рядом, могут скрываться и другие открытия, подобные тесту Агравала — Каяла — Саксены и основанные на таких же простых идеях, как полиномиальная версия теоремы Ферма (и не важно, что пока о них никто даже не подозревает), может оказаться, что системы шифрования, основанные на разложении числа на простые множители, не настолько надежны, как нам хочется верить. Так что пока не стоит раскрывать в Интернете кличку вашей кошки!

Даже элементарная математика простых чисел ведет к выдвижению более сложных концепций. Евклид доказал, что простые числа уходят в бесконечность, так что невозможно просто перечислить их все и успокоиться. Мы не можем также дать простую и практичную алгебраическую формулу для вычисления всех простых чисел подряд, примерно так, как по формуле x² вычисляются квадраты чисел. (Простые формулы существуют, но они «мошенничают», встраивая в формулу сами простые числа под разными личинами, и в результате не сообщают нам ничего нового.) Пытаясь познать природу этих неуловимых и странных чисел, мы экспериментируем, ищем в них признаки структурированности и пытаемся доказать, что найденные нами закономерности присутствуют во всех простых числах, какими бы большими они ни были. Можно, к примеру, задаться вопросом о том, как простые числа распределены среди всех целых чисел. Таблицы простых чисел позволяют предположить, что чем дальше, тем таких чисел становится меньше. В табл. 1 показано, сколько простых чисел содержится в разных диапазонах на 1000 последовательных целых чисел.

Таблица 1. Количество простых чисел в последовательных интервалах по 1000 чисел

Числа во второй колонке по большей части уменьшаются сверху вниз, хотя иногда ненадолго изменяют свое поведение: к примеру, после 114 мы видим 117.