Великая Теорема Ферма - Аверьянова Н. Л. "Zenzen". Страница 26

Хотя бесконечность количества простых чисел навсегда разрушила надежды на скорое доказательство Великой теоремы Ферма, такой большой запас простых чисел пригодился, например, в таких областях как шпионаж или исследование жизни насекомых. Прежде чем мы вернемся к повествованию о поиске доказательства Великой теоремы Ферма, уместно немного отвлечься и познакомиться с тем, как правильно и неправильно используются простые числа.

Теория простых чисел — одна из немногих областей чистой математики, которые нашли непосредственное приложение в реальном мире, а именно в криптографии. Криптография занимается кодированием секретных посланий с таким расчетом, чтобы декодировать их мог только получатель, а перехватчик расшифровать бы их не мог. Процесс кодирования требует использования ключа к шифру, и по традиции для дешифровки необходимо снабдить получателя этим ключом. При такой процедуре ключ — самое слабое звено в цепи обеспечения безопасности. Во-первых, получатель и отправитель должны условиться о деталях ключа, и обмен информацией на этом этапе сопряжен с определенным риском. Если противнику удастся перехватить ключ при обмене информацией, то он сможет дешифровывать все последующие послания. Во-вторых, для поддержания безопасности ключи необходимо регулярно менять, и при каждой замене ключа существует риск перехвата нового ключа противником.

Проблема ключа вращается вокруг того факта, что применение ключа в одну сторону приводит к шифровке послания, а применение того же ключа в обратную сторону дешифрует послание — дешифровка производится столь же легко, как и шифровка. Но из опыта нам известно, что ныне существуют многие ситуации, когда дешифровка гораздо сложнее, чем шифровка: приготовить яичницу-болтунью несравненно легче, чем вернуть яичницу-болтунью в исходное состояние, разделив белки и желтки.

В 70-е годы XX века Уитфилд Диффи и Мартин Хеллман занялись поиском математического процесса, который было бы легко выполнить в одну сторону, но невероятно трудно — в противоположную сторону. Такой процесс дал бы идеальный ключ. Например, у меня мог бы быть мой собственный ключ из двух частей, и его шифровальную часть я мог бы опубликовать в общедоступном месте. После этого любой желающий мог бы посылать мне зашифрованные послания, но дешифровальная часть ключа была бы известна только мне. И хотя шифровальная часть ключа была бы доступна всем, к дешифровальной части она не имела бы никакого отношения.

В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман — группа математиков и специалистов по компьютерам из Массачусеттского технологического института — выяснили, что простые числа являются идеальным базисом для процесса легкой шифровки и трудной дешифровки. Чтобы изготовить мой собственный персональный ключ, я мог бы взять два огромных простых числа, каждое из которых содержит до 80 знаков, и, умножив одно число на другое, получить еще большее составное число. Все, что требуется для кодирования посланий, — это знать большое составное число, тогда как для дешифровки послания необходимо знать два исходных простых числа, которые мы перемножили, т. е. простые множители составного числа. Я могу позволить себе опубликовать большое составное число — шифровальную половину ключа, и сохранить в тайне два простых множителя — дешифровальную половину ключа. Очень важно, что хотя любому известно большое составное число, разложить его на два простых множителя чрезвычайно трудно.

Рассмотрим более простой пример. Предположим, что я выбрал и сообщил всем желающим составное число 589, позволяющее каждому посылать мне шифрованные послания. Два простых множителя числа 589 я сохранил бы в тайне, поэтому расшифровать послания никто, кроме меня, не может. Если бы кому-нибудь удалось найти два простых множителя числа 589, то такой человек также смог бы дешифровывать адресованные мне послания. Но сколь ни мало число 589, найти его простые множители не так-то просто. В данном случае на настольном компьютере в несколько минут можно было бы обнаружить, что простые множители числа 589 равны 31 и 19 (31·19 = 589), поэтому мой ключ не мог бы гарантировать безопасность переписки особенно долго.

Но если бы составное число, которое я опубликовал, содержало более сотни знаков, это делало бы поиск простых множителей практически неразрешимой задачей. Даже если для разложения огромного составного числа (шифровального ключа) на два простых множителя (дешифровального ключа) использовать самые мощные компьютеры, которые только существуют в мире, то и тогда, чтобы найти эти множители, понадобилось бы несколько лет. Следовательно, чтобы сорвать коварные планы иностранных шпионов, мне необходимо всего лишь ежегодно менять ключ. Раз в год я довожу до всеобщего сведения свое новое гигантское составное число, и тогда всякий, кто пожелает попытать счастья и расшифровать мои послания, будет вынужден приступать заново к разложению опубликованного числа на два простых множителя.

Простые числа встречаются и в мире живой природы. У периодических цикад, известных как Magicicada septendecim, самый длинный жизненный цикл из всех насекомых. Их жизнь начинается под землей, где личинки терпеливо сосут соки из корней деревьев. И лишь через 17 лет ожидания взрослые цикады появляются из-под земли, собираются в огромные рои и на какое-то время заполоняют все вокруг. За несколько недель они спариваются, откладывают яйца, а затем умирают.

Вопрос, который не давал биологам покоя, — почему жизненный цикл у цикад такой длинный? Имеет ли какое-нибудь значение для жизненного цикла то, что продолжительность его выражается простым числом лет? Другой вид — Magicicada tredecim — роится через каждые 13 лет. Это наводит на мысль, что продолжительность жизненного цикла, выражающаяся простым числом лет, дает виду определенные эволюционные преимущества.

Согласно одной теории, у цикады имеется паразит, также обладающий длинным жизненным циклом. Цикада, естественно, стремится избавиться от паразита. Если паразит обладает жизненным циклом продолжительностью, скажем 2 года, то цикада стремится избежать жизненного цикла, продолжительность которого в годах делится на 2, так как в противном случае цикада, появляясь из-под земли, и паразит регулярно встречались бы. Аналогично, если бы паразит обладал жизненным циклом продолжительностью 3 года, то цикада стремилась бы избегать жизненных циклов, продолжительность которых в годах выражалась числом, кратным 3. Следовательно, чтобы избежать совпадений с паразитом, лучшей стратегией для цикады было бы иметь жизненный цикл, длящийся простое число лет. Так как ни одно целое число (кроме 1 и 17) не делит число 17, Magicicada septendecim очень редко встречается со своим паразитом. Если продолжительность жизненного цикла паразита составляет 2 года, то цикада встречается с ним только раз в 34 года, а если продолжительность жизненного цикла паразита больше, например, составляет 16 лет, то его встреча с цикадой происходит лишь раз в 272 (= 16·17) года.

«Реванш» для паразита возможен только в двух случаях: при его годичном жизненном цикле и при жизненном цикле продолжительностью 17 лет. Маловероятно, однако, что паразит выживет на протяжении 17 своих поколений подряд, так как первым 16 поколениям будет не на ком паразитировать. С другой стороны, чтобы достичь 17-летней продолжительности жизненного цикла, поколениям паразита необходимо пройти в своей эволюции 16-летний жизненный цикл. Это означало бы, что на каком-то этапе эволюции паразит и цикада не встречались бы на протяжении 272 лет! И в том, и в другом случае большой жизненный цикл продолжительностью в простое число лет способствуют выживанию цикады.

Возможно, именно этим и объясняется, что пресловутый паразит так никогда и не был найден! В гонке на выживание с цикадой паразит, по-видимому, постоянно увеличивал продолжительность своего жизненного цикла до тех пор, пока не наткнулся на 16-летний барьер. После этого паразит на протяжении 272 лет не мог встретиться со своей жертвой и за это время вымер. В результате появилась цикада с жизненным циклом длиной 17 лет. Необходимость в более продолжительном жизненном цикле для цикады отпала, поскольку паразит более не существовал.