«Майкл, это Воган. Я получил результат этих экспериментов. Бери ручку с бумагой и записывай». И у него вышло, что 2400 – 593 – простое число. Обозначим как k произведение всех простых чисел p, меньших 300. Числа k × 338 + 821 и k × 338 + 823 – числа-близнецы[31]. Это были самые большие из известных на тот момент чисел-близнецов. У меня волосы встали дыбом! Это было невероятно! Это было просто невероятно.
Тест Миллера – Рабина на простоту чисел, как теперь известно, дает возможность быстро определить, являются ли простыми даже огромные числа, с произвольно заданной степенью точности.
Здесь мы могли бы задаться философским вопросом о значении слова «являться». Мы так привыкли к тому, что математика – царство точности, что не можем допустить мысли о том, что число может быть «вероятно простым» или «почти определенно простым». Какая достоверность достаточно достоверна? На практике современные шифровальные системы – те, что шифруют интернет-подключения и цифровые транзакции, – настроены на ложноположительные результаты в одном случае на миллион миллиардов миллиардов. Другими словами, это десятичная дробь, начинающаяся с двадцати четырех нулей после запятой, – и это меньше одного ложного простого числа на все количество песчинок на земле. Это значение получается после всего лишь сорока применений теста Миллера – Рабина. Вы действительно никогда не можете быть абсолютно уверены, но вы можете подойти очень близко к этому состоянию. И очень быстро.
Даже если вы никогда не слышали о тесте Миллера – Рабина, о нем хорошо осведомлены ваш ноутбук, планшет или телефон. Спустя несколько десятилетий с момента открытия он все еще остается основным методом, используемым для поиска и проверки простых чисел во многих областях. Он незримо работает, когда вы расплачиваетесь кредитной картой онлайн, и задействован практически каждый раз, когда защищенные коммуникации передаются по воздуху или по проводам.
В течение многих лет после открытия Миллера и Рабина оставалось неясным, будет ли когда-нибудь изобретен эффективный алгоритм для проверки простоты чисел по детерминированным стандартам с абсолютной точностью. В 2002 году такой метод был открыт Маниндрой Агравалом, Нираджем Каялом и Нитином Саксеной в Индийском институте технологий, но рандомизированные алгоритмы, подобные тесту Миллера – Рабина, работают гораздо быстрее и сегодня используются чаще всего.
Что же касается некоторых других задач, случайность по-прежнему остается единственным ключом к эффективным решениям. Вот один любопытный математический пример, известный как проверка полиномиального тождества. Если есть два многочлена: 2