Алгоритмы для жизни: Простые способы принимать верные решения - [86]

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

Рандомизированные алгоритмы

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

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

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

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

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

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