Карта → линии → сквозной сюжет

Бесполезная наука

как самая чистая часть математики стала инфраструктурой связи — и что ей теперь грозит

Открыть на карте

1. 1
   Александрия ок. 300 г. до н. э.

   Евклид: простых чисел бесконечно много

   Завязка: простых бесконечно много — значит, материал не кончится никогда

   Три арифметические книги «Начал»: алгоритм наибольшего общего делителя, работающий до сих пор; доказательство бесконечности простых — вопреки распространённому мнению, не от противного, а конструктивное; и половина теоремы о совершенных числах, вторую половину которой докажут через две тысячи лет.

2. 2
   Александрия ок. 240 г. до н. э.

   Эратосфен: решето и размер Земли

   Первый способ их добывать — и он до сих пор лежит внутри всякой библиотеки

   Заведующий Александрийской библиотекой придумывает способ выписывать простые числа подряд — им пользуются до сих пор без изменений — и в те же годы измеряет окружность Земли по разнице длины теней, ошибившись на считанные проценты.

3. 3
   Тулуза письмо от 18 октября 1640

   Малая теорема Ферма

   Теорема без единого применения — через три века станет проверкой на простоту

   Если $p$ просто и $a$ на него не делится, то $a^{p-1}-1$ делится на $p$. Доказательства Ферма, по обыкновению, не привёл. На этом утверждении, обобщённом Эйлером, стоит вся современная криптография с открытым ключом.

4. 4
   Санкт-Петербург 1732–1749

   Эйлер: от числа Ферма до дзета-функции

   И функция Эйлера, которая окажется в самом показателе ключа

   Эйлер разрушает гипотезу Ферма одним делителем 641, доказывает теорему о двух квадратах после семи лет попыток и находит тождество, связывающее сумму по всем числам с произведением по всем простым. Последнее — вторжение анализа в теорию чисел, из которого выйдет всё дальнейшее.

5. 5
   Париж 1876

   Люка: рекордное простое — вручную

   Во что обходились большие простые вручную: девятнадцать лет на одно число

   Эдуард Люка доказывает простоту числа $2^{127}-1$ — тридцать девять цифр — придуманным им же тестом, без единой вычислительной машины. Рекорд продержится 75 лет. Тот же тест сегодня находит рекордные простые в проекте, где участвуют десятки тысяч компьютеров.

6. 6
   Челтнем (GCHQ) 1969–1974

   Челтнем: секретная криптография, запрещённый приоритет

   Секретная линия: всё придумано — и положено в стол на четверть века

   В британской службе радиоразведки за пять лет придумали криптографию с открытым ключом целиком: идею, реализацию и обмен ключами. Всё засекретили. Когда через двадцать три года разрешили рассказать, автор идеи не дожил трёх недель.

7. 7
   Стэнфорд «New Directions in Cryptography» — ноябрь 1976

   Диффи и Хеллман: ключ, который можно опубликовать

   Открытая линия: то же самое, но вслух и на два года позже

   До 1976 года всякий шифр требовал заранее переданного ключа: для тысячи абонентов это полмиллиона мешков с секретами. Диффи и Хеллман показали, как двое вырабатывают общий секрет, обмениваясь числами в открытую. Самой системы шифрования у них не было — только понятие и работающий протокол обмена.

8. 8
   Кембридж (Массачусетс) 1977

   RSA: теория чисел уходит в каждый смартфон

   Развязка: «бесполезная» часть математики становится инфраструктурой связи

   Малая теорема Ферма в обобщении Эйлера превращается в шифр, у которого ключ шифрования можно публиковать. Харди в 1940 году гордился тем, что теория чисел не имеет применений; через тридцать семь лет она стала инфраструктурой цивилизации.

9. 9
   Сиэтл 1985, независимо: доклад Миллера на CRYPTO в августе (Йорктаун-Хайтс) и работа Коблица (Сиэтл)

   Коблиц и Миллер: секущая Диофанта в каждом рукопожатии

   Та же схема на другой группе — и ключ помещается в банковский чип

   Сложение точек эллиптической кривой — та самая секущая, которой Диофант искал рациональные решения, — оказалось группой, где дискретное логарифмирование труднее, чем в остатках по модулю. Ключ выходит короче в двенадцать раз при той же стойкости, и сегодня на этом стоит почти всякое защищённое соединение.

10. 10
    Мюррей-Хилл (Bell Labs) доклад на симпозиуме FOCS — ноябрь 1994; журнальная версия — 1997

    Шор: разложение на множители за полином — но не на этой машине

    Обратный удар: у всего построенного обнаруживается срок годности

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