Первым человеком, продемонстрировавшим удивительно широкое применение метода рандомизации в информатике, стал Майкл Рабин. Родившийся в 1931 году в Бреслау в Германии (который впоследствии стал польским Вроцлавом в конце Второй мировой войны), Рабин был потомком целой династии раввинов. Его семья переехала из Германии в Палестину в 1935 году, и там он отказался от протоптанной для него отцом раввинской тропы в пользу красоты математики, открыв для себя исследования Алана Тьюринга на заре студенчества в Еврейском университете и эмигрировав в США, где впоследствии он окончил Принстон. Рабин должен был получить премию Тьюринга – аналог Нобелевской премии в сфере информатики – за включение в теоретическую информатику недетерминированных случаев, когда автомат не обязан следовать одному параметру, но имеет несколько возможных путей следования. В 1975 году, находясь в творческом отпуске, Рабин пришел в MIT в поисках нового направления для работы.

Нашел он его в одной из старейших задач: как найти простые числа. Алгоритмами поиска простых чисел интересовались еще в Древней Греции, где математики использовали простой и точный метод, получивший название «решето Эратосфена». Оно работает следующим образом: чтобы найти все простые числа меньше n, начните записывать последовательность чисел от 1 до n по порядку. Затем вычеркните все числа, кратные 2, кроме самого числа 2 (4, 6, 8, 10, 12 и т. д.). Найдите следующее самое маленькое число, которое еще не было вычеркнуто (в данном случае – 3), и вычеркивайте все числа, кратные ему (6, 9, 12, 15). Продолжайте в том же духе, и те числа, что останутся в результате, и будут простыми числами.

На протяжении тысячелетий изучение простых чисел считалось, как выразился Г. Х. Харди, «одним из самых очевидно бесполезных разделов математики». Но оно неожиданно приобрело большую практическую значимость в XX веке, став ключевым моментом в области шифрования и сетевой безопасности. Гораздо проще перемножать простые числа между собой, чем выносить их за скобки. С достаточно большими простыми числами – например, состоящими из тысячи знаков – умножение может быть произведено в долю секунды, в то время как разложение на множители могло бы занять буквально миллионы лет. Это и есть то, что зовется односторонней (необратимой) функцией, обратное значение которой очень трудно вычислить. В современном шифровании данных, к примеру, секретные простые числа, известные только отправителю и получателю, перемножаются между собой, чтобы создать огромные составные числа. Последние могут быть переданы публично без опасений, поскольку обратное разложение зашифрованного послания на множители займет у любого перехватчика слишком много времени, чтобы стоило хотя бы попытаться. Таким образом, любая безопасная онлайн-коммуникация – будь то торговля, банкинг или электронные сообщения – начинается с охоты на простые числа.

Такое применение простых чисел в шифровании данных внезапно сделало алгоритмы их поиска и проверки невероятно важными. Решето Эратосфена хоть и эффективно, но не обладает высоким коэффициентом полезного действия. Если вы хотите проверить, является ли некое определенное число простым, то согласно стратегии решета вам следует попытаться разделить его на все простые числа вплоть до его квадратного корня. Проверка, является ли шестизначное число простым, потребует деления на все 168 простых чисел меньше 1000 – не так уж и плохо. Но проверка двенадцатизначного числа потребует деления на 78 498 простых чисел меньше миллиона, и это деление быстро выходит из-под контроля. Простые числа, используемые в современном шифровании, состоят из сотен знаков. Забудьте об этом.

В MIT Рабин встретился с Гари Миллером, недавним выпускником кафедры информатики в Беркли. В своей докторской диссертации Миллер разработал интригующе перспективный, гораздо более быстрый алгоритм проверки простых чисел. Но существовала небольшая проблемка: он не всегда срабатывал.

Миллер вывел множество уравнений (выраженных в виде двух чисел – n и x), которые всегда верны, если число n является простым, независимо от того, какие значения будет иметь x. Если они выйдут неверными хотя бы для одного значения x, то число n никак не может быть простым (в этих случаях x называют «свидетелем» против простоты). Проблема заключается в ложных положительных результатах: даже если n не является простым числом, в отдельных случаях уравнение все равно может получиться верным. Это поначалу поставило подход Миллера под сомнение.

Рабин понял, что в данной ситуации шаг за пределы обычного «детерминированного» мира информатики может стать весьма значимым. Если число n не является простым, сколько возможных значений x дадут ложноположительный ответ, объявив n простым числом? Ответ, как показал Рабин, – одна четвертая. Так что для случайного значения x, если уравнение Миллера выходит верным, шанс, что число n не является простым, равен одному из четырех. И самое главное, каждый раз, когда мы берем случайное значение x и проверяем уравнение Миллера, вероятность, что число n только кажется простым, но не является таковым, снижается еще на одно число, кратное четырем. Повторите процедуру 10 раз, и вероятность ложноположительного результата будет равна одной четверти в десятой степени – меньше, чем один шанс из миллиона. Все еще не хватает достоверности? Проверьте еще пять раз, и вероятность снизится до одной миллиардной.

Воган Пратт, еще один информатик из MIT, применил алгоритм Рабина на практике. Однажды зимним вечером, когда Рабин отмечал с друзьями Хануку, ему позвонил Пратт. Рабин вспоминает тот полуночный звонок:

Тест Миллера – Рабина на простоту чисел, как теперь известно, дает возможность быстро определить, являются ли простыми даже огромные числа, с произвольно заданной степенью точности.

Здесь мы могли бы задаться философским вопросом о значении слова «являться». Мы так привыкли к тому, что математика – царство точности, что не можем допустить мысли о том, что число может быть «вероятно простым» или «почти определенно простым». Какая достоверность достаточно достоверна? На практике современные шифровальные системы – те, что шифруют интернет-подключения и цифровые транзакции, – настроены на ложноположительные результаты в одном случае на миллион миллиардов миллиардов. Другими словами, это десятичная дробь, начинающаяся с двадцати четырех нулей после запятой, – и это меньше одного ложного простого числа на все количество песчинок на земле. Это значение получается после всего лишь сорока применений теста Миллера – Рабина. Вы действительно никогда не можете быть абсолютно уверены, но вы можете подойти очень близко к этому состоянию. И очень быстро.

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

В течение многих лет после открытия Миллера и Рабина оставалось неясным, будет ли когда-нибудь изобретен эффективный алгоритм для проверки простоты чисел по детерминированным стандартам с абсолютной точностью. В 2002 году такой метод был открыт Маниндрой Агравалом, Нираджем Каялом и Нитином Саксеной в Индийском институте технологий, но рандомизированные алгоритмы, подобные тесту Миллера – Рабина, работают гораздо быстрее и сегодня используются чаще всего.

Что же касается некоторых других задач, случайность по-прежнему остается единственным ключом к эффективным решениям. Вот один любопытный математический пример, известный как проверка полиномиального тождества. Если есть два многочлена: 2x3 + 13x2 + 22x + 8 и (2x + 1) × (x + 2) × (x + 4) – и вычисление обоих будет произведено фактически одним и тем же способом: произвести все умножения, затем сравнить результаты, – то это займет слишком много времени, тем более что число переменных растет.

И снова случайность приходит на помощь: просто возьмите случайные значения числа x и подставьте в выражение. Если два выражения не тождественны, то будет большим совпадением, если вы получите один и тот же ответ при подстановке случайно выбранных значений. И будет еще бóльшим совпадением, если вы снова получите одинаковый ответ, подставив случайные значения во второй раз. И куда бóльшим совпадением, если это произойдет трижды подряд. Так как не существует ни одного известного детерминированного алгоритма для эффективной проверки полиномиального тождества, то этот рандомизированный метод (с многочисленными повторениями, позволяющими максимально приблизиться к «почти точности») – единственный практический из имеющихся.