Большинство задач, подобных расчету взаимодействий субатомных частиц или шансов на победу в пасьянсе, сами по себе являются вероятностными, так что их решение с помощью рандомизированного подхода вроде метода Монте-Карло вполне разумно. Но, пожалуй, самым удивительным доказательством важности рандомизированного подхода служит тот факт, что он может быть использован в таких ситуациях, где случайность, казалось бы, вовсе не играет никакой роли. Даже если ваш вопрос предполагает четкий ответ «да» или «нет», «истина» или «ложь» и тут не может быть никаких вероятностей, бросок пары кубиков способен по-прежнему стать частью принятия решения.
Рандомизированные алгоритмы
Первым человеком, продемонстрировавшим удивительно широкое применение метода рандомизации в информатике, стал Майкл Рабин. Родившийся в 1931 году в Бреслау в Германии (который впоследствии стал польским Вроцлавом в конце Второй мировой войны), Рабин был потомком целой династии раввинов. Его семья переехала из Германии в Палестину в 1935 году, и там он отказался от протоптанной для него отцом раввинской тропы в пользу красоты математики, открыв для себя исследования Алана Тьюринга на заре студенчества в Еврейском университете и эмигрировав в США, где впоследствии он окончил Принстон. Рабин должен был получить премию Тьюринга – аналог Нобелевской премии в сфере информатики – за включение в теоретическую информатику недетерминированных случаев, когда автомат не обязан следовать одному параметру, но имеет несколько возможных путей следования. В 1975 году, находясь в творческом отпуске, Рабин пришел в MIT в поисках нового направления для работы.
Нашел он его в одной из старейших задач: как найти простые числа. Алгоритмами поиска простых чисел интересовались еще в Древней Греции, где математики использовали простой и точный метод, получивший название «решето Эратосфена». Оно работает следующим образом: чтобы найти все простые числа меньше n, начните записывать последовательность чисел от 1 до n по порядку. Затем вычеркните все числа, кратные 2, кроме самого числа 2 (4, 6, 8, 10, 12 и т. д.). Найдите следующее самое маленькое число, которое еще не было вычеркнуто (в данном случае – 3), и вычеркивайте все числа, кратные ему (6, 9, 12, 15). Продолжайте в том же духе, и те числа, что останутся в результате, и будут простыми числами.
На протяжении тысячелетий изучение простых чисел считалось, как выразился Г. Х. Харди, «одним из самых очевидно бесполезных разделов математики». Но оно неожиданно приобрело большую практическую значимость в XX веке, став ключевым моментом в области шифрования и сетевой безопасности. Гораздо проще перемножать простые числа между собой, чем выносить их за скобки. С достаточно большими простыми числами – например, состоящими из тысячи знаков – умножение может быть произведено в долю секунды, в то время как разложение на множители могло бы занять буквально миллионы лет. Это и есть то, что зовется односторонней (необратимой) функцией, обратное значение которой очень трудно вычислить. В современном шифровании данных, к примеру, секретные простые числа, известные только отправителю и получателю, перемножаются между собой, чтобы создать огромные составные числа. Последние могут быть переданы публично без опасений, поскольку обратное разложение зашифрованного послания на множители займет у любого перехватчика слишком много времени, чтобы стоило хотя бы попытаться. Таким образом, любая безопасная онлайн-коммуникация – будь то торговля, банкинг или электронные сообщения – начинается с охоты на простые числа.