Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

Такое применение простых чисел в шифровании данных внезапно сделало алгоритмы их поиска и проверки невероятно важными. Решето Эратосфена хоть и эффективно, но не обладает высоким коэффициентом полезного действия. Если вы хотите проверить, является ли некое определенное число простым, то согласно стратегии решета вам следует попытаться разделить его на все простые числа вплоть до его квадратного корня[30]. Проверка, является ли шестизначное число простым, потребует деления на все 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 и подставьте в выражение. Если два выражения не тождественны, то будет большим совпадением, если вы получите один и тот же ответ при подстановке случайно выбранных значений. И будет еще бóльшим совпадением, если вы снова получите одинаковый ответ, подставив случайные значения во второй раз. И куда бóльшим совпадением, если это произойдет трижды подряд. Так как не существует ни одного известного детерминированного алгоритма для эффективной проверки полиномиального тождества, то этот рандомизированный метод (с многочисленными повторениями, позволяющими максимально приблизиться к «почти точности») – единственный практический из имеющихся.

Проверка полиномиального тождества демонстрирует, что зачастую нам лучше сосредоточить усилия на расчете случайных величин (например, значений двух выражений, о которых мы хотим что-то узнать), чем пытаться распутать хитросплетения их внутренних взаимосвязей. Это кажется более-менее наглядным. Если вам дадут пару непонятных гаджетов и попросят определить, два ли это разных устройства или копии одного и того же, большинство из нас скорее начнут нажимать на разные кнопки, нежели взломают корпус и начнут рассматривать соединения проводов. И мы не особенно удивляемся, когда киношный наркобарон вскрывает ножом несколько упаковок наугад, чтобы удостовериться в качестве всей партии.