Путеводитель для влюбленных в математику - [7]
(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)
Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу создания шифров. Криптографическая система с открытым ключом[26] устроена так, что можно раскрыть метод шифровки сообщений, но это не облегчит расшифровку засекреченных текстов. Мы не станем сейчас погружаться в детали метода, но основная идея состоит в том, что в процессе шифрования используется составное число N, представляющее собой произведение двух огромных простых чисел: N = P × Q. Расшифровка требует знания конкретных простых чисел P и Q. Если мы знаем N, этого достаточно для шифровки, но не для декодирования, а найти его простые множители все еще чрезвычайно сложно.
Мы используем криптографическую систему с открытым ключом всякий раз, когда совершаем покупки в интернете. Прежде чем браузер вышлет продавцу номер нашей кредитной карты, он получает от продавца открытый ключ шифрования. Браузер шифрует номер карты с помощью метода, о котором мы рассказывали. Если перехватить ключ, это ничего не даст, потому что метод шифровки не говорит о методе расшифровки (а его знает только продавец). Когда зашифрованное сообщение приходит на компьютер продавца, индивидуальный метод расшифровки раскрывает номер карты лишь законному получателю информации.
Криптографическая система с открытым ключом имеет и военные применения, вплоть до системы приведения в боевую готовность ядерного оружия[27].
211 591 = 457 × 463.
Глава 2
Двоичная система счисления[28]
Древних римлян часто поминают дурным словом за их громоздкую систему записи чисел. Люди не любят римские числа, так как они обременяют вычисления. Никто не обрадуется перспективе перемножать XLVII и DCDXXIV. А вот задача умножить 47 на 924 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).
Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел обрел новое воплощение. Что легче прочесть?
• Реновация школ в нашем округе обойдется в 23000000 долларов.
• Реновация школ в нашем округе обойдется в 23 млн долларов.
Разумеется, я не стал разделять разряды в первом случае, чтобы число было сложнее прочесть (и я попал в точку, не правда ли?). Но, даже если проставить пробелы, фраза «Пентагон требует дополнительные 19 000 000 000 долларов» сложнее для восприятия, чем «Пентагон требует дополнительные 19 млрд долларов». Иногда удобнее использовать слова вместо чисел.
Мнимое преимущество позиционной системы счисления[29] – это то, что в ней проще производить вычисления. Но давайте задумаемся о том, сколько сил уходит на перемножение двух чисел. Во-первых, нам необходимо запоминать дополнительные математические данные. К тому же мы обязаны помнить таблицу умножения. Во-вторых, мы проделываем многоуровневую процедуру: сортируем числа по разрядам, умножаем по соответствующему правилу, получаем промежуточные данные, складываем.
Да, десятичные числа легче перемножать, чем их римские аналоги, однако это по-прежнему утомительно. Возникает вопрос, есть ли способ записывать числа, который бы облегчал вычисления. Мы выяснили, что да, есть, но для этого придется пожертвовать наглядностью.
Простейший способ записи чисел – единичная система счисления: мы просто записываем столько же символов (будем использовать цифру 1), сколько единиц в интересующем нас числе. Например, число 3 окажется трехзначным: 111. Сложение и умножение становятся исключительно простыми. Чтобы сложить 3 и 5, мы просто запишем два числа, 111 и 11111, друг за другом (без пробела) – и вот он, ответ: 11111111. Умножать тоже просто. Мы запишем одно число вертикально, а другое горизонтально и получим следующую таблицу:
Затем мы заполним таблицу, поставив единичку в каждом столбце и в каждой колонке:
Наконец, мы выпишем все единички в ряд и получим ответ: 111111111111111. Складывать и перемножать числа в единичной системе счисления существенно проще, чем десятичные или римские числа[30].
Разумеется, такая простота вычислений дается ценой титанических затрат внимания и времени. Никому не захочется прибегать к этому методу, чтобы перемножить 47 и 924.
Числа, записанные в двоичной системе счисления[31], не так привычны нам, как десятичные или римские, но с ними проще делать вычисления. Вот почему в компьютерах используется именно двоичная система. Чтобы разобраться, как она устроена, нам нужно припомнить особенности десятичной системы.
Для записи чисел в десятичной системе счисления используют десять символов, располагаемых в разных комбинациях в ряд по горизонтали. Значение символа зависит от его места в ряду. 29 и 92 означают разные числа, потому что 2 и 9 занимают разные позиции. 29 означает «два десятка и девять единиц». 5804 означает «пять тысяч, восемь сотен, ни одного десятка и четыре единицы». Позиция цифры в десятичном числе означает, на какую степень десяти
