Страница 5 из 6
2, 3, 5, 7, 11, 13, …, P.
Пусть N – результат перемножения всех этих чисел:
N = 2 × 3 × 5 × 7 × 11 × 13 × … × P.
Теперь давайте подумаем обо всех числах от 1 до N включительно. Каждое из них (за исключением 1) делится на одно или несколько простых чисел; иными словами, любое число (кроме 1) делится на какое-то простое число.
Сколько чисел от 1 до N делится на 2? Очевидно, что половина (четные числа). Вычеркнем их и оставим лишь нечетные:
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, …
Количество целых чисел между 1 и N, которые мы вычеркнули, равно N / 2.
Вычеркнем из оставшихся чисел те, которые делятся на 3. Вот что получится:
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, …
Мы удалили треть оставшихся чисел[24]. Осталось две трети, а от изначального количества –
Продолжим в том же духе и вычеркнем числа, делящиеся на 5, удалив таким образом пятую часть оставшихся чисел. Получится чисел. Вот что останется:
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, …
Дальше мы вычеркиваем числа, делящиеся на 7, оставив шесть седьмых от нашего перечня, и будем двигаться по этому пути, пока не дойдем до числа P.
В конце концов количество тех чисел, которые мы не вычеркнули, станет равно
Так как все числа от 1 до N, кроме 1, делятся на какое-то простое число, выражение (C) должно быть равно 1. Верно? Вспомним, что N = 2 × 3 × 5 × 7 × 11 × 13 × … × P, подставим это произведение в выражение (C) и перегруппируем множители:
Это дает 1 × 2 × 4 × 6 × … × (P – 1), что существенно больше 1! Выражение (C) должно быть равно 1, но очевидным образом не равно 1. Ошибка заключалась в изначальном предположении о том, что количество простых чисел конечно. Следовательно, их бесконечно много.
Есть много захватывающих вопросов о простых числах. Здесь я расскажу про две самые печально известные проблемы.
Хотя простых чисел бесконечно много, они встречаются все реже и реже, когда мы последовательно двигаемся от единицы к бесконечности. Позже (в главе 7) мы проанализируем среднюю разность между двумя соседними большими простыми числами. Однако простые числа все равно часто встречаются рядом, отличаясь на две и более единицы (единственная пара с отличием на один – 2 и 3). Если простые числа отличаются на две единицы, их называют простыми числами-близнецами, или парными простыми числами. Наименьшая пара близнецов – числа 3 и 5. Между 1 и 10 000 есть 205 пар близнецов, последние – числа 9929 и 9931.
Вопрос: простых чисел-близнецов бесконечно много?
Надо признать, что это неизвестно до сих пор.
Вот другой вопрос. Принято считать, что впервые его поставил немецкий математик Кристиан Гольдбах (1690–1764). Ему стало любопытно: какие четные числа (кроме 2) можно представить в качестве суммы двух простых? Вот пример:
Вопрос: можем ли мы продолжать этот ряд бесконечно? Гольдбах предположил, что любое четное число (за исключением 2) представляет собой сумму двух простых.
Но на самом деле мы до сих пор не знаем этого наверняка.
Изучение простых чисел относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».
Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?
Пусть 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 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).
Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел обрел новое воплощение. Что легче прочесть?
• Реновация школ в нашем округе обойдется в 23000000 долларов.
• Реновация школ в нашем округе обойдется в 23 млн долларов.
Разумеется, я не стал разделять разряды в первом случае, чтобы число было сложнее прочесть (и я попал в точку, не правда ли?). Но, даже если проставить пробелы, фраза «Пентагон требует дополнительные 19 000 000 000 долларов» сложнее для восприятия, чем «Пентагон требует дополнительные 19 млрд долларов». Иногда удобнее использовать слова вместо чисел.
24
Вообще говоря, это утверждение надо доказать. В частности, надо доказать, что удалена точно, а не приблизительно треть. – Прим. науч. ред.
25
Дадим зарок не пользоваться ничем, кроме карандаша и бумаги, и попробуем самостоятельно убедиться в том, что перемножать простые числа сравнительно легко, а раскладывать их произведение на множители – сложно. Для начала умножим 227 на 281. Если ни на что не отвлекаться, можно найти шестизначный ответ за пару минут. А теперь попробуйте найти без калькулятора два трехзначных простых множителя числа 211 591. Это не так-то просто. Ответ будет в конце главы.
26
Термин «открытый ключ» означает, что раскрытие алгоритма шифрования – ключ к нему находится в открытом доступе – еще не рассекречивает сообщение. Один из таких алгоритмов изобрели в 1970-е Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman); по первым буквам их фамилий метод назвали RSA.
27
Криптографические системы на основе перемножения простых чисел будут эффективны лишь до тех пор, пока ученые не усовершенствуют квантовые компьютеры, где логические элементы (кубиты) могут находиться в состоянии 0 и 1 одновременно. Теоретически так называемый алгоритм Шора с помощью квантового компьютера способен разложить большое число на простые множители почти так же быстро, как происходит само шифрование. – Прим. пер.
Несмотря на то что математики уже больше ста лет знают, что решение задачи о трисекции угла с помощью слепой линейки и циркуля невозможно, все время находятся энтузиасты, предлагающие очередное «решение». Анализ самых остроумных попыток можно найти в книге Андервуда Дадли «Смета трисекций» (A Budget of Trisections).
Один из них равен – i, потому что (– i) × (– i) × (– i) = (– i)³ = i. Но чему равны другие два? Ответ вы найдете в конце главы.
28
Популярный слоган на футболке математика: «Все люди делятся на 10 категорий: те, кто понимает двоичную систему счисления, и те, кто в ней ничего не смыслит». Когда вы прочтете эту главу, вы тоже сможете шутить в этом духе.