Путеводитель для влюбленных в математику. Эдвард Шейнерман
относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».
Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?
Пусть P и Q – два больших простых числа, скажем стозначных. Перемножить их – титанический труд для человека, но компьютер может посчитать произведение N = P × Q мгновенно. В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении. Никто не знает эффективного алгоритма разложения таких огромных чисел на простые множители[25].
(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)
Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу создания шифров. Криптографическая система с открытым ключом[26] устроена так, что можно раскрыть метод шифровки сообщений, но это не облегчит расшифровку засекреченных текстов. Мы не станем сейчас погружаться в детали метода, но основная идея состоит в том, что в процессе шифрования используется составное число N, представляющее собой произведение двух огромных простых чисел: N = P × Q. Расшифровка требует знания конкретных простых чисел P и Q. Если мы знаем N, этого достаточно для шифровки, но не для декодирования, а найти его простые множители все еще чрезвычайно сложно.
Мы используем криптографическую систему с открытым ключом всякий раз, когда совершаем покупки в интернете. Прежде чем браузер вышлет продавцу номер нашей кредитной карты, он получает от продавца открытый ключ шифрования. Браузер шифрует номер карты с помощью метода, о котором мы рассказывали. Если перехватить ключ, это ничего не даст, потому что метод шифровки не говорит о методе расшифровки (а его знает только продавец). Когда зашифрованное сообщение приходит на компьютер продавца, индивидуальный метод расшифровки раскрывает номер карты лишь законному получателю информации.
Криптографическая система с открытым ключом имеет и военные применения, вплоть до системы приведения в боевую готовность ядерного оружия[27].
211 591 = 457 × 463.
Глава 2
Двоичная система счисления[28]
Древних римлян часто поминают дурным словом за их громоздкую систему записи чисел. Люди не любят римские числа, так как они обременяют вычисления. Никто не обрадуется перспективе перемножать XLVII и DCDXXIV. А вот задача умножить 47 на 924 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).
Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел
Дадим зарок не пользоваться ничем, кроме карандаша и бумаги, и попробуем самостоятельно убедиться в том, что перемножать простые числа сравнительно легко, а раскладывать их произведение на множители – сложно. Для начала умножим 227 на 281. Если ни на что не отвлекаться, можно найти шестизначный ответ за пару минут. А теперь попробуйте найти без калькулятора два трехзначных простых множителя числа 211 591. Это не так-то просто. Ответ будет в конце главы.
Термин «открытый ключ» означает, что раскрытие алгоритма шифрования – ключ к нему находится в открытом доступе – еще не рассекречивает сообщение. Один из таких алгоритмов изобрели в 1970-е Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman); по первым буквам их фамилий метод назвали RSA.
Криптографические системы на основе перемножения простых чисел будут эффективны лишь до тех пор, пока ученые не усовершенствуют квантовые компьютеры, где логические элементы (кубиты) могут находиться в состоянии 0 и 1 одновременно. Теоретически так называемый алгоритм Шора с помощью квантового компьютера способен разложить большое число на простые множители почти так же быстро, как происходит само шифрование. –
Несмотря на то что математики уже больше ста лет знают, что решение задачи о трисекции угла с помощью слепой линейки и циркуля невозможно, все время находятся энтузиасты, предлагающие очередное «решение». Анализ самых остроумных попыток можно найти в книге Андервуда Дадли «Смета трисекций» (A Budget of Trisections).
Один из них равен –
Популярный слоган на футболке математика: «Все люди делятся на 10 категорий: те, кто понимает двоичную систему счисления, и те, кто в ней ничего не смыслит». Когда вы прочтете эту главу, вы тоже сможете шутить в этом духе.