Такое применение простых чисел в шифровании данных внезапно сделало алгоритмы их поиска и проверки невероятно важными. Решето Эратосфена хоть и эффективно, но не обладает высоким коэффициентом полезного действия. Если вы хотите проверить, является ли некое определенное число простым, то согласно стратегии решета вам следует попытаться разделить его на все простые числа вплоть до его квадратного корня[30]. Проверка, является ли шестизначное число простым, потребует деления на все 168 простых чисел меньше 1000 – не так уж и плохо. Но проверка двенадцатизначного числа потребует деления на 78 498 простых чисел меньше миллиона, и это деление быстро выходит из-под контроля. Простые числа, используемые в современном шифровании, состоят из сотен знаков. Забудьте об этом.
В MIT Рабин встретился с Гари Миллером, недавним выпускником кафедры информатики в Беркли. В своей докторской диссертации Миллер разработал интригующе перспективный, гораздо более быстрый алгоритм проверки простых чисел. Но существовала небольшая проблемка: он не всегда срабатывал.
Миллер вывел множество уравнений (выраженных в виде двух чисел – n и x), которые всегда верны, если число n является простым, независимо от того, какие значения будет иметь x. Если они выйдут неверными хотя бы для одного значения x, то число n никак не может быть простым (в этих случаях x называют «свидетелем» против простоты). Проблема заключается в ложных положительных результатах: даже если n не является простым числом, в отдельных случаях уравнение все равно может получиться верным. Это поначалу поставило подход Миллера под сомнение.
Рабин понял, что в данной ситуации шаг за пределы обычного «детерминированного» мира информатики может стать весьма значимым. Если число n не является простым, сколько возможных значений x дадут ложноположительный ответ, объявив n простым числом? Ответ, как показал Рабин, – одна четвертая. Так что для случайного значения x, если уравнение Миллера выходит верным, шанс, что число n не является простым, равен одному из четырех. И самое главное, каждый раз, когда мы берем случайное значение x и проверяем уравнение Миллера, вероятность, что число n только кажется простым, но не является таковым, снижается еще на одно число, кратное четырем. Повторите процедуру 10 раз, и вероятность ложноположительного результата будет равна одной четверти в десятой степени – меньше, чем один шанс из миллиона. Все еще не хватает достоверности? Проверьте еще пять раз, и вероятность снизится до одной миллиардной.
Воган Пратт, еще один информатик из MIT, применил алгоритм Рабина на практике. Однажды зимним вечером, когда Рабин отмечал с друзьями Хануку, ему позвонил Пратт. Рабин вспоминает тот полуночный звонок: