Подход с позиций грубой силы

Подход с позиций грубой силы

Когда в 1940 году Г.Г. Харди заявил о том, что самая первоклассная математика в основном бесполезна, он тут же был вынужден добавить, что это не обязательно плохо: «Настоящая математика не оказывает влияния на ведение войн. Никто еще не открыл ни одного применения теории чисел в военных целях». Вскоре выяснилось, что Харди заблуждался.

В 1944 году Джон фон Нейман в соавторстве с Оскаром Моргенштерном написал книгу «Теория игр и экономическое поведение», в которой ввел придуманный им термин «теория игр». Фон Нейман попытался использовать математику для описания структуры игр и того, как люди играют в них. Он начал с шахмат и покера, а затем попытался построить модели более сложных игр — таких, как экономика. После второй мировой войны корпорация RAND оценила потенциал идей фон Неймана и пригласила его принять участие в разработке стратегии холодной войны. С той поры математическая теория игр стала основным средством, с помощью которого генералы проверяют разрабатываемые ими стратегии, рассматривая вооруженные конфликты как усложненный вариант шахматных партий. Простой иллюстрацией применения теории игр к анализу военных операций служит задача о труэли.

Труэль аналогична дуэли, но с тремя участниками вместо двух. Однажды утром м-р Блэк, м-р Грей и м-р Уайт вздумали решить конфликт труэлью на пистолетах. Стрелять условились до тех пор, пока в живых не останется только один из участников. М-р Блэк стрелял хуже всех. В цель он попадал в среднем лишь один раз из трех. М-р Уайт стрелял лучше всех — без промаха. Чтобы уравнять шансы участников труэли, м-ру Блэку разрешено стрелять первым, за ним должен стрелять м-р Грей (если он останется в живых), затем мог стрелять м-р Уайт (если он еще будет жив).

Далее все начиналось снова, и так до тех пор, пока в живых не останется только один из участников труэли. Вопрос: в кого должен выстрелить м-р Блэк, производя свой первый выстрел? Вы можете попытаться ответить на этот вопрос, опираясь на свою интуицию, но лучше все же, если ваш ответ будет основан на теории игр. Решение задачи см. в Приложении 9.

Большое значение в военное время приобрела математическая теория криптографии — наука о конструировании и «взламывании» кодов. Во время второй мировой войны союзники поняли, что математическая логика может оказаться полезной для дешифровки немецких радиограмм, если только вычисления проводить достаточно быстро. Требовалось автоматизировать математические вычисления, чтобы их могла производить машина, и более других способствовал раскрытию немецких кодов английский математик Алан Тьюринг.

В 1938 году Тьюринг вернулся в Кембридж после стажировки в Принстонском университете. Он стал свидетелем того переполоха, который вызвали теоремы Гёделя о неразрешимости, и принял участие в попытках спасти осколки мечты Гильберта.

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

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

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

«В 1937 году было установлено, что в отличие от своих японских и итальянских аналогов, германская армия, германский военно-морской флот, возможно, германские военно-воздушные силы вместе с другими государственными организациями, вроде железных дорог и СС, использовали для всех нужд, кроме тактических коммуникаций, различные версии одной и той же шифровальной системы — шифровальной машины «Энигма», выпущенной на рынок в 20-е годы. Надежность ее немцы повышали, внося различные усовершенствования. В 1937 году Правительственной школе кодов и шифров удалось раскрыть устройство менее модифицированной и менее надежной модели машины «Энигма», используемой германскими, итальянскими и испанскими вооруженными силами. Не считая этого случая, «Энигма» до сих пор выдерживала все попытки раскрыть ее устройство. Весьма вероятно, что эти попытки будут продолжены».

Шифровальная машина «Энигма» состояла из клавиатуры, соединенной с шифровальным узлом. Шифровальный узел содержал три отдельных ротора. Положения роторов определяли, как шифруется каждая литера на клавиатуре. Раскрыть код «Энигма» было так трудно потому, что число внутренних состояний, в которых могла находиться машина, было необычайно велико. Во-первых, три ротора в машине можно было выбирать из пяти, заменять и переставлять, чтобы сбить с толку тех, кто попытается раскрыть код. Во-вторых, каждый ротор мог находиться в одном из двадцати шести. различных положений. Все это означало, что машина может находиться более чем в миллионе различных состояний. Кроме перестановок букв, производимых роторами, соединения на плате в тыльной стороне машины можно было менять вручную, что позволяло устанавливать машину более чем в 1,5·10²⁰ возможных состояний. Чтобы еще больше увеличить надежность, три ротора постоянно изменяли ориентацию так, что после кодирования и передачи одной буквы при кодировании следующей буквы машина устанавливалась в новое состояние. Например, набрав на клавиатуре «DODO», мы получим кодированное сообщение «FGTB», так как хотя буквы «D» и «O» встречаются в сообщении дважды, кодируются они всякий раз по-другому.

Машины «Энигма» были взяты на вооружение германской армией, военно-морским флотом и военно-воздушными силами, а также использовались на железных дорогах и в других правительственных учреждениях. Подобно всем системам кодов того времени, «Энигма» имела слабое место: получатель должен был знать, как установлена машина отправителя. Для обеспечения безопасности установку «Энигмы» требовалось менять ежедневно. Один из способов, позволявших отправителю ежедневно менять код и сообщать его получателю, заключался в публикации установок машины на каждый день в секретной кодовой книге. Риск при такой системе состоял в том, что англичане могут захватить какую-нибудь немецкую подводную лодку и захватить кодовую книгу с ежедневными установками машины на следующий месяц. Альтернативный подход, который использовался на протяжении большей части войны, состоял в том, чтобы установка машины на текущий день сообщалась в преамбуле к сообщению и декодировалась с помощью кода на предыдущий день.

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

Криптография представляет собой борьбу умов между составителем кода и тем, кто пытается этот код разгадать. Составитель кода видит свою задачу в том, чтобы каждое исходящее от отправителя сообщение было закодировано настолько надежно, чтобы раскодировать его было невозможно даже в том случае, если оно будет перехвачено противником. Однако существует верхний предел для количества возможных математических манипуляций, поскольку сообщения должны доходить до получателя быстро и эффективно. Сила германского кода «Энигма» заключалась в том, что кодируемое сообщение подвергалось кодировке на нескольких уровнях с очень высокой скоростью. Тот, кто стремился раскрыть, или «взломать», код, видел свою задачу, в том, чтобы взять перехваченное сообщение и разгадать код, причем скорость расшифровки была весьма существенна: германское сообщение, содержащее приказ потопить британский корабль, должно было быть декодировано до того, как корабль потонет.

Тьюринг возглавил группу математиков, в задачу которых входило воссоздать точную копию машины «Энигма». Все свои абстрактные идеи предвоенной поры Тьюринг воплотил в устройстве, которое теоретически могло методично, одну за другой, перебирать все возможные установки машины «Энигма» до тех пор, пока код не окажется раскрытым. Для проверки всех потенциально возможных состояний машины «Энигма» математики из Бличли парка использовали британские машины около двух метров в высоту и примерно столько же в ширину, работавшие на электромеханических реле. Непрестанное тиканье реле стало причиной, по которой эти машины получили свое прозвище — их стали называть бомбами. Несмотря на максимальное по тем временам быстродействие, «бомбы» не могли перебрать за разумное время все гигантское количество возможных вариантов установки «Энигма», поэтому группе Тьюринга предстояло найти способы, позволяющие существенно сократить число перестановок, по крохам собирая любую информацию, которую можно было извлечь из перехваченных сообщений.

Одно из существенных достижений группы из Бличли парка стало осознание того, что машина «Энигма» никогда не кодировала букву самой буквой, т. е. если отправитель набирал на клавиатуре литеру «R», то машина потенциально могла отправить любую другую букву (в зависимости от установки машины), кроме буквы «R». Это, на первый взгляд незначительное, обстоятельство позволило резко сократить время, необходимое для того, чтобы декодировать сообщение. Немцы нанесли ответный удар, ограничив длину предаваемых сообщений. Все сообщения неизбежно содержат в себе какие-то зацепки, позволяющие «взломщикам кодов» декодировать сообщения. Чем длиннее сообщение, тем больше зацепок оно содержит. Установив предельный объем для всех сообщений — не более 250 знаков, немцы надеялись компенсировать «нежелание» машины «Энигма» кодировать букву той же буквой.

Чтобы взломать германские коды, Тьюринг часто пытался отгадать в сообщениях ключевые слова. Если ему это удавалось, то декодирование остальной части сообщения многократно ускорялось. Например, если взломщики кода подозревали, что сообщение содержит сводку погоды (метеоданные часто передавались в кодированных сообщениях), то они могли предположить, что в сообщении содержатся такие слова, как «туман» или «скорость ветра». Если их догадка оправдывалась, то они быстро декодировали остальное сообщение и тем самым могли судить об установке «Энигмы» на день передачи сообщения. Тогда в этот день и другие, более ценные, сообщения декодировались без труда.

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

1 февраля 1942 года немцы установили дополнительный, четвертый, ротор на машине «Энигма», предназначенный для передачи особо секретной информации. Это было самое большое повышение уровня кодирования за время войны, но группа Тьюринга сумела парировать этот ход немцев, увеличив эффективность своих «бомб». Благодаря усилиям сотрудников Школы кодов и шифров, союзники знали о противнике больше, чем могли подозревать немцы. Эффективность операций германских подводных лодок сильно уменьшилась, и британцам удалось предупредить налеты германских ВВС. Взломщикам кодов из Бличли парка также удалось перехватить и декодировать сообщения, содержавшие точные координаты вспомогательных кораблей германского ВМФ, что позволило послать британские бомбардировщики и потопить эти корабли.

Союзникам приходилось принимать особые меры предосторожности для того, чтобы неожиданные атаки не выдали их осведомленности и чтобы немцы не догадались о том, что их сообщения могут быть декодированы. Если бы немцы заподозрили, что система «Энигма» поддается декодированию, то они могли бы повысить уровень кодирования, и англичане оказались бы на исходных позициях. Поэтому в ряде случаев Школа кодов и шифров информировала военных о планируемой атаке, но командование предпочитало не принимать особых контрмер. Ходили даже слухи, что Черчиллю было известно о готовящемся опустошительном налете на Ковентри, но он предпочел не принимать особых мер предосторожности, чтобы немцы ничего не заподозрили. Стюарт Милнер-Барри, работавший вместе с Тьюрингом, опровергает эти слухи и утверждает, что сообщение о готовящемся налете на Ковентри удалось декодировать, когда уже было поздно.

Ограниченное использование декодированной информации работало идеально. Даже когда англичане использовали перехваченные сообщения для предотвращения тяжелых потерь, немцы не заподозрили, что код «Энигма» раскрыт. Немцы были убеждены, что их уровень кодирования настолько высок, что раскрыть их коды абсолютно невозможно. Свои огромные потери немцы относили за счет агентов британской секретной службы, якобы проникших в высшие ряды немецкого командования.

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

Но и в самый разгар своей деятельности в качестве взломщика кодов Тьюринг не забывал о своих чисто математических исследованиях. На смену воображаемым машинам пришли реальные, но тонкие вопросы, доступные пониманию только посвященных, оставались нерешенными. К концу войны Тьюринг оказал помощь в постройке «Колосса» — полностью электронной вычислительной машины, на 1500 электронных лампах, работавших гораздо быстрее, чем электромеханические реле, которые использовались в «бомбах». «Колосс» был компьютером в современном смысле слова. Необычайное (по тем временам) быстродействие и достаточно высокая сложность «Колосса» навели Тьюринга на мысль рассматривать эту вычислительную машину как примитивный мозг: «Колосс» обладал памятью, он мог обрабатывать информацию, и внутренние состояния компьютера напоминали состояния человеческого мозга. Свою воображаемую машину Тьюринг превратил в первый реально действующий компьютер.

По окончании второй мировой войны Тьюринг продолжал строить все более сложные вычислительные машины, такие, как Automatic Computing Engine (ACE) — Автоматическую вычислительную машину. В 1948 году Тьюринг перешел на работу в Манчестерский университет и построил первый в мире компьютер с программой, которая хранилась в электронном виде. Благодаря Тьюрингу, Британия стала обладательницей самых мощных компьютеров в мире, но он прожил он недостаточно долго для того, чтобы увидеть наиболее выдающиеся успехи компьютерных вычислений.

В послевоенные годы Тьюринг находился под наблюдением Intelligence Service. Разведчики, считая Тьюринга гомосексуалистом и опасаясь, что человек, знающий о британских секретных кодах больше, чем кто-либо другой, может стать объектом шантажа, следили за каждым его шагом. Тьюринг даже смирился, что неотступно находится под колпаком у разведслужб, но в 1952 году был арестован за нарушение британских законов о гомосексуалистах. Это унижение стало для Тьюринга последней каплей, переполнившей его терпение. Эндрю Ходжес, биограф Тьюринга, так описывает событие, приведшее к его смерти: «Смерть Алана Тьюринга стала сильнейшим потрясением для всех, кто его знал… То, что он был несчастным человеком, находившимся в состоянии нервного напряжения, что он консультировался у психиатра и, как и многие другие, перенес удар, — все это было ясно. Но суд состоялся два года назад, лечение гормонами закончилось годом раньше, и он, казалось, стал выше всего этого.

Расследование, произведенное 10 июня 1954 года, установило, что это было самоубийство. Тьюринга нашли лежащим навзничь в постели. Вокруг его рта была пена. Патологоанатом, проводивший посмертное вскрытие, определил причину смерти как отравление цианидом калия… В доме находился сосуд с цианидом калия и еще один сосуд с раствором цианида. Рядом с кроватью лежала половинка яблока со следами укусов. Анализ яблока не производился».

* * *

Наследием Тьюринга стал компьютер, способный производить за несколько часов вычисления, которые заняли бы у человека непозволительно много времени. Современные компьютеры успевают за долю секунды произвести больше арифметических операций, чем Ферма сделал за всю свою жизнь. Те математики, которые все еще вели неравную борьбу с Великой теоремой Ферма, начали компьютерную атаку на проблему, полагаясь на компьютерную версию подхода, развитого Куммером в XIX веке.

Куммер, обнаружив пробел в работах Коши и Ламе, установил, что трудностей при доказательстве Великой теоремы Ферма удается избежать, если показатель n равен нерегулярному простому числу (при n, не превышающих числа 100, нерегулярны только простые числа 37, 59 и 67). В то же время, Куммер показал, что теоретически все случаи с нерегулярными значениями показателя n могут быть рассмотрены индивидуально. Единственная проблема заключается лишь в том, что каждый случай требует огромного объема вычислений. Сколь велик объем вычислений наглядно демонстрирует то, что Куммер и его коллега Дмитрий Мириманов потратили три недели, чтобы выполнить все вычисления для трех нерегулярных простых чисел, не превышающих числа 100. Но ни они, ни другие математики не были готовы к тому, чтобы приступить к вычислениям для следующей группы нерегулярных простых чисел в интервале от 100 до 1000.

Через несколько десятилетий проблемы, связанные с огромным объемом вычислений, стали существенно более доступными. С появлением компьютера большому объему вычислений, связанных с доказательством Великой теоремы Ферма, стало возможно противопоставить быстродействие вычислительных машин. И после второй мировой войны группы программистов и математиков доказали Великую теорему Ферма при всех значениях n до 500, затем до 1000, а позже до 10000. В 80-е годы Сэмюэль С. Вагстафф из университета Пурду поднял предел до 25 000, а совсем недавно математики заявили, что Великая теорема Ферма верна при всех значениях n до 4 миллионов.

И хотя нематематикам могло бы показаться, что положение с доказательством Великой теоремы Ферма, наконец, стало лучше, математическое сообщество сознавало, что успех носит чисто косметический характер. Даже если бы суперкомпьютеры провели десятилетия в непрерывных вычислениях, доказывая Великую теорему Ферма при значениях n одно за другим, то и тогда им не удалось бы доказать теорему для каждого значения n до бесконечности, и поэтому никто не мог бы утверждать, что Великая теорема Ферма доказана во всей общности. Ведь даже если бы теорему удалось доказать для n до миллиарда, то и тогда не было бы никаких причин, по которым она должна была бы быть верна для n, равного миллиарду плюс один. Если бы теорему удалось доказать для n до триллиона, то нет причин, по которым она должна была бы быть верна для n, равного триллиону плюс один, и т. д. до бесконечности. Бесконечность недостижима за счет одной лишь грубой силы — перемалывания чисел с помощью компьютера.

Дэвид Лодж в своей книге «Странствия в картинках» приводит красочное описание вечности, имеющее отношение к аналогичному понятию бесконечности: «Представьте себе стальной шар размером со Вселенную и муху, которая садится на него раз в миллион лет. Когда этот стальной шар обратится в пыль от трения, вечность еще даже не начнется». Тем не менее, результаты, полученные с помощью компьютеров, свидетельствовали в пользу Великой теоремы Ферма. Поверхностному наблюдателю могло показаться, что этих результатов предостаточно, но сколько бы ни было данных, любое их количество не могло удовлетворить математиков — сборище скептиков, которые не признают ничего, кроме абсолютного доказательства. Экстраполяция теории на бесконечное множество чисел, опирающаяся на результаты, полученные для конечного количества чисел, — игра рискованная (и неприемлемая).

Насколько опасна такая экстраполяция с конечного множества на бесконечное показывает одна последовательность простых чисел. В XVIII веке математики доказали, что все следующие числа простые:

31, 331, 3 331, 33 331, 333 331, 3 333 331, 33 333 331.

Следующие числа становились все б?льшими гигантами, и проверка их на простоту потребовала бы значительных усилий. Некоторые математики поддались искушению выдать замеченную закономерность за правило и предположили, что все числа указанного вида простые. Но уже следующее число 333 333 331 оказалось составным: 333 333 331 = 17·19 607 843.

Другим хорошим примером, показывающим почему не следует доверять только результатам компьютерных расчетов, может служить гипотеза Эйлера. Эйлер предположил, что уравнение

x⁴ + y⁴ + z⁴ = w⁴,

аналогичное уравнению Ферма, не имеет ненулевых решений в целых числах. На протяжении двух столетий никому не удавалось доказать гипотезу Эйлера, как, впрочем, и опровергнуть ее контрпримером. Ни первые вычисления вручную, ни долгие годы просеивания чисел с помощью компьютеров не позволили обнаружить ни одного решения. Отсутствие контрпримера воспринималось как убедительное свидетельство в пользу гипотезы Эйлера. Но в 1988 году Наум Элькис из Гарвардского университета нашел следующее решение:

2 682 440⁴ + 15 365 639⁴ + 187 960⁴ = 20 615 673⁴.[15]

Несмотря на все «подкрепляющие» данные гипотеза Эйлера оказалась ложной. В действительности Элькис доказал, что это уравнение имеет бесконечно много решений в целых числах. Мораль ясна: нельзя использовать результаты, полученные для первого миллиона целых чисел, как обоснование гипотезы относительно всех целых чисел.

Но обманчивый характер гипотезы Эйлера — ничто по сравнению с гипотезой о завышенной оценке количества простых чисел. Рассматривая все б?льшие и б?льшие целые числа, мы убеждаемся, что найти среди них простые числа становится все труднее. Например, между 0 и 100 расположены 25 простых чисел, тогда как между 10 000 000 и 10 000 100 — только 2 простых числа. В 1791 году Карл Гаусс, которому было тогда всего лишь четырнадцать лет, сформулировал приближенный закон, по которому уменьшается частота простых чисел. Формула Гаусса давала разумную точность, но всегда слегка завышала истинное распределение простых чисел. Проверка на простых числах до миллиона, миллиарда или триллиона показала, что гипотеза Гаусса излишне щедра, и математики испытывали сильнейшее искушение считать, что так будет и для всех чисел до бесконечности. Так родилась гипотеза о завышенной оценке распределения простых чисел.

В 1914 году Дж. И. Литлвуд, сотрудник Г.Г. Харди по Кембриджскому университету доказал, что для очень больших чисел формула Гаусса даст заниженную оценку распределения простых чисел. В 1955 году С. Скьюз показал, что недооценка количества простых чисел может наступить прежде, чем будет достигнуто число

Это число невозможно даже представить, и никаких практических приложений оно не имеет. Харди назвал число Скьюза «самым большим числом, которое когда-либо служило какой-нибудь цели в математике». Харди подсчитал, что если бы кто-нибудь вздумал сыграть в шахматы со всеми частицами во Вселенной (а их 10⁸⁷; под ходом в такой игре следовало бы понимать перестановку любых двух частиц), то число возможных партий оказалось бы приближенно равно числу Скьюза.

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