Соловей и Штрассен: монетка вместо доказательства

До сих пор в этой истории случайность была предметом изучения и источником затруднений. Здесь она впервые становится инструментом — и обнаруживается, что бросок монеты даёт то, чего не даёт доказательство.

Задача

Дано число в триста цифр. Простое оно или составное?

Перебор делителей отпадает сразу: делителей до корня примерно $10^{150}$, а во Вселенной около $10^{80}$ атомов. Между тем ответ нужен постоянно и быстро: шифр с открытым ключом начинается с того, что надо найти два больших простых числа, а искать их можно только так — брать наугад нечётное число и спрашивать, простое ли оно.

Свидетель

Отправная точка — малая теорема Ферма: если $p$ простое и $a$ на него не делится, то

$$a^{\,p-1} \equiv 1 \pmod p .$$

Отсюда проверка: возьмём наугад $a$, посчитаем $a^{\,n-1} \bmod n$. Возведение в степень делается быстрым способом — примерно $\log_2 n$ умножений, для трёхсот цифр это около тысячи операций, доли секунды.

Если получилось не $1$ — число $n$ точно составное. Обратите внимание, что мы при этом узнали: составность доказана, а ни одного делителя не найдено. Число $a$ называют свидетелем.

Беда в том, что бывают числа, у которых свидетелей по ФермаПьер Фермафранцузский юрист и математик · 1607–1665Советник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей. нет вовсе. Наименьшее — $561 = 3 \cdot 11 \cdot 17$: для всякого $a$, взаимно простого с ним, сравнение выполняется, хотя число составное. Такие числа называются числами Кармайкла, и в 1994 году доказано, что их бесконечно много.

Починка и откуда берётся половина

Соловей и Штрассен заменили проверку на более строгую. Для нечётного простого $n$ верен критерий ЭйлераЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя.:

$$a^{\,(n-1)/2} \;\equiv\; \left(\frac{a}{n}\right) \pmod n,$$

где справа — символ ЯкобиКарл Густав Якобинемецкий математик · 1804–1851Соперничал с Абелем в теории эллиптических функций и придумал вместе с Бесселем вещь, изменившую науку сильнее любой теоремы, — исследовательский семинар., который считается быстро, взаимностью, без всякого разложения на множители.

Теорема. Если $n$ — нечётное составное, то это сравнение нарушается не менее чем для половины значений $a$ из $1, \dots, n-1$.

И вот главное, ради чего стоит разбирать этот сюжет в классе. Половина берётся не из статистики и не из опыта. Те $a$, которые сравнению удовлетворяют, образуют подгруппу в группе обратимых остатков; для составного $n$ она собственная, то есть не совпадает со всей группой. А по теореме ЛагранжаЖозеф Луи Лагранжфранцузский математик и механик итальянского происхождения · 1736–1813Написал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней. порядок подгруппы делит порядок группы, значит собственная подгруппа занимает не больше половины. Всё.

Вероятность $1/2$ здесь — следствие теоремы Лагранжа о порядке подгруппы, а не результат подсчёта частот. Случайность работает не потому, что мир так устроен, а потому, что лжесвидетелей мало по алгебраической причине.

Арифметика уверенности

Возьмём $k$ независимых случайных $a$. Составное число проскочит все проверки с вероятностью не больше $2^{-k}$.

При $k = 100$ это $2^{-100} \approx 10^{-30}$.

Сравните с чем-нибудь житейским: вероятность того, что за время счёта космическая частица перевернёт бит в памяти машины и испортит ответ, на много порядков больше. Ответ, полученный сотней бросков монеты, надёжнее ответа, полученного длинным доказательством, которое проверяла та же машина.

Это переворот в отношении к достоверности, и он произошёл тихо. Уверенность перестала быть свойством «доказано — не доказано» и стала числом, которое назначает пользователь.

Что было дальше

Гари Миллер в 1976 году предложил проверку, которая была бы детерминированной — но её обоснование опирается на недоказанную обобщённую гипотезу РиманаБернхард Риманнемецкий математик · 1826–1866Прожил тридцать девять лет и оставил около десяти работ — из которых выросли современная геометрия, теория функций комплексного переменного и главная нерешённая задача математики.. Михаэль Рабин в 1980 году сделал из неё вероятностную, без всяких гипотез, с вероятностью ошибки не больше $1/4$ на свидетеля. Тест Миллера — Рабина и работает сегодня всюду, где выдаётся ключ.

А в 2002 году Агравал, Каял и Саксена нашли то, чего искали тридцать лет: детерминированный полиномиальный алгоритм проверки на простоту, безо всяких гипотез и безо всякой случайности. И это ничего не изменило: он слишком медленный. Случайность оказалась не нужна в принципе — и осталась нужна на практике.

Через двадцать лет выяснится, что так, возможно, обстоит дело со всеми вероятностными алгоритмами сразу.

О людях

Роберт Соловей (род. 1938) — прежде всего теоретик множеств: его имя носит модель, в которой все множества действительных чисел измеримы, и метод случайного форсинга. Заметьте совпадение: человек, придумавший, как добавлять к теории множеств «случайное» действительное число, придумал и как проверять простоту броском монеты.

Фолькер Штрассен уже встречался нам на карте — это он показал, что гауссово исключение не оптимально, а умножать матрицы можно быстрее школьного способа. Тот же человек, тот же ход мысли: не улучшать перебор, а сменить постановку.

⚠ Гари Миллера, автора теста, не следует путать с Виктором Миллером, который приспособил эллиптические кривые к криптографии, — это разные люди.