Тайны чисел: Математическая одиссея

Как это ни поразительно, вы можете честно бросать монету через интернет. Такая возможность появляется благодаря математике простых чисел. Все простые числа нечетны за исключением 2 (это странное простое число, ведь лишь оно четно). Если мы разделим одно из этих нечетных простых чисел на 4, то получим в остатке 1 или 3. Например, остаток от деления 17 на 4 равен 1, а при делении 23 на 4 в остатке получается 3.

Как мы узнали в главе 1, две тысячи лет назад древние греки доказали, что существует бесконечно много простых чисел. Но существует ли бесконечно много тех из них, которые дают при делении на 4 остаток 1, или бесконечно много дающих остаток 3? Это один из тех вопросов, которые Пьер де Ферма поставил перед математиками 350 лет назад, однако ответ был дан лишь в XIX в. немецким математиком Густавом Лежёном Дирихле. Используя очень сложный математический аппарат, он сумел доказать, что половина простых чисел дает остаток 1, а другая половина 3 – никакой из остатков не оказывается предпочтительнее. Впрочем, не совсем легко понять, что математики имеют в виду под половиной, когда речь идет о бесконечном множестве. Но, по существу, это означает, что если вы возьмете простые числа, меньшие заданного большого числа, то почти в точности половина из них даст при делении на 4 остаток 1.

Итак, остаток 1 или 3 при делении простого числа на 4 не более «предвзят», чем выпадение орла или решки при подкидывании честной монеты. Для изучения нашей задачи по бросанию монеты давайте отождествим орлы с простыми числами, дающими остаток 1 при делении на 4, а с решками мы отождествим простые числа, дающие остаток 3. А теперь последует искусный математический пассаж. Если я возьму два простых числа, скажем 17 и 41, оба из которых относятся к орлам – они дают остаток 1 при делении на 4, – и перемножу их, то произведение также будет характеризоваться остатком 1 при делении на 4. Например, 41 × 17 = 697 = 174 × 4 + 1. Если же я возьму два простых числа, скажем 23 и 43, оба из набора решек – они дают остаток 3 при делении на 4… то получится не то, чего вы могли бы ожидать. У произведения этих двух чисел при делении на 4 также будет остаток 1: в данном случае 23 × 43 = 989 = 247 × 4 + 1. Итак, произведение простых чисел не дает намека на то, взяты ли сомножители из набора орлов или из набора решек. Этим свойством мы можем воспользоваться, чтобы играть в «орла или решку по интернету».

Если я подброшу монету и выпадет орел, я выберу два простых числа из набора орлов и перемножу их. Если выпадет решка, я выберу два простых числа из набора решек и перемножу их. После того как я подкинул свою монету и сделал вычисления, я посылаю ответ моему сопернику в Токио. Оказалось, что он равен 6497. Поскольку ответ при делении на 4 всегда дает остаток 1, мой соперник не может, не зная простых чисел, сказать, выбрал ли я их из набора орлов или же из набора решек. Теперь он может сказать «орел» или «решка».

Чтобы мой соперник убедился, что он выиграл или проиграл, мне достаточно будет выслать ему два выбранных мною простых числа. В данном случае ими были 89 и 73, два простых числа из набора орлов. Поскольку никакие другие числа при перемножении не дадут 6497, то я предоставил ему достаточно информации, чтобы доказать, что я не жульничал. С другой стороны, я не предоставил ему достаточно информации, чтобы мой соперник мог жульничать.

На самом деле это не совсем верно. Если соперник сумеет разложить 6497 на простые множители 89 и 73, то он поймет, что нужно сказать «орел». Но, если я буду выбирать достаточно большие простые числа (много-много бо́льшие двузначных чисел), то будет почти невозможно даже с современными вычислительными возможностями разложить произведение на простые множители. Схожий принцип используется в кодах, которые защищают номера кредитных карт, посылаемые через интернет.

Легкое задание

Я бросил монету, выбрал два простых числа из набора орлов или из набора решек и перемножил их. У меня получилось число 13 068 221. Что выпало? Орел или решка? Постарайтесь найти ответ без компьютера (решение приведено в конце главы).

Трудное задание

А что скажете, если получилось число

5 759 602 149 240 247 876 857 994 004 081 295 363 338

151 725 852 938 901 132 472 828 171 992 873 665 524 051

005 072 817 707 778 665 601 229 693?

На этот раз можно использовать компьютер.

Почему разложение чисел означает взлом кода?