A−1Ac = c.
Боб не знает ни A, ни A–1.
Аналогично замки Боба соответствуют шифрам B и B–1, известным только ему, таким, что B–1Bc = c.
С учетом этих предварительных замечаний метод соответствует следующей процедуре:
1. Алиса пересылает все 52 числа Ac1, …, Ac52 Бобу. Он понятия не имеет, каким картам эти числа соответствуют; по существу, Алиса перетасовала колоду.
2. Боб «сдает» пять карт Алисе и пять самому себе. Он высылает Алисе ее карты. Чтобы упростить запись, рассмотрим лишь одну из этих карт, обозначив ее Ac. Алиса может выяснить значение c, применив к полученному числу A–1, так что она знает, какие карты ей сданы.
3. Бобу необходимо выяснить, какие карты он выбрал для себя, но только Алиса знает, как извлечь истинные значения из зашифрованных. Но Боб не может послать свои карты Алисе, потому что тогда она будет знать, что у него в руке. Поэтому к каждой своей карте Ad он применяет свое шифровальное правило, чтобы получить BAd, и высылает результат такой обработки Алисе.
4. Алиса может вновь применить свое правило A–1, чтобы «снять замок», но на этот раз ее ждет засада: результат будет равен A–1BAd.
В обычной алгебре мы могли бы поменять A–1 и B местами, чтобы получить
BA–1Ad,
что равняется Bd.
После этого Алиса могла бы выслать результат обратно Бобу, а тот, в свою очередь, применил бы B–1, чтобы получить d.
Однако функции нельзя переставлять таким образом. К примеру, если Ac = c + 1 (и, соответственно, A–1c = c – 1) и Bc = c², то A–1Bc = Bc – 1 = c²– 1, тогда как
BA–1c = (A –1c)² = (c – 1)² = c²– 2c + 1,
то есть совсем не то же самое.
Чтобы обойти это препятствие, следует избегать подобных функций и выбирать такие методы шифрования, для которых A–1B = BA–1. В этом случае говорят, что для функций A и B действует коммутативный закон, поскольку все это несложно привести к эквивалентному условию AB = BA. Обратите внимание: в описанном нами физическом методе замки Алисы и Боба и правда позволяют перестановку. Их можно навешивать и снимать в любом порядке, результат будет тот же: ящичек с двумя замками.
Таким образом, Алиса и Боб могут играть в покер по переписке, если сумеют придумать два допускающих перестановку шифра A и B, таких, чтобы алгоритм расшифровки A –1 был известен только Алисе, а алгоритм B–1 – только Бобу.
Боб и Алиса выбирают большое простое число p, которое может быть опубликовано и известно всем. Они согласуют также 52 числа c1, …, c52 (mod p), которые будут представлять карты.
Алиса выбирает некоторое число a от 1 до p – 2 и определяет свою кодирующую функцию A как Ac = ca (mod p).
Пользуясь базовой теорией чисел, можно сказать, что обратная (декодирующая) функция имеет вид
A–1c = ca' (mod p)
для некоего числа a', которое она может вычислить. Алиса держит и a, и a' в секрете.
Аналогично Боб выбирает себе число b и определяет свою кодирующую функцию B как Bc = cb (mod p) и обратную к ней
B–1c = cb' (mod p)
для числа b', которое он может вычислить. Он держит b и b' в секрете.
Кодирующие функции A и B подчиняются коммуникативному закону, поскольку
ABc = A (cb) = (cb)a = cba = cab = (ca)b = B (ca) = BAc,
где все равенства выполняются (mod p). Поэтому Алиса и Боб могут использовать A и B описанным образом.
Исключение невозможного
Из мемуаров доктора Ватсапа
– Ватсап!
– А? Что? Вы это мне, Сомс?
– Сколько раз можно повторять, Ватсап, чтобы вы не приносили журнал The Strand в этот дом!
– Но… как…
– Вы знаете мои методы. Вы нетерпеливо постукивали пальцами, как делаете обычно, пока меня дожидаетесь. При этом вы то и дело поглядывали на свернутую газету, которая торчит у вас из кармана пальто. Газета эта слишком толста для Daily Reporter, хотя именно это название красуется у нее на первой полосе, так что в нее, наверное, завернут какой-то журнал. А поскольку вы по привычке прячете от меня лишь один журнал, сомневаться в его природе не приходится.
– Простите, Сомс, я просто надеялся получить кое-какие сравнительные данные о методах исследования из произведений коллеги… э-э… шарлатана из дома напротив.
– Тьфу! Этот человек – мошенник! Жулик, называющий себя детективом!
Откровенно говоря, временами Сомс бывает невыносим. Если подумать, он почти всегда такой.
– Бывали случаи, когда мне удавалось случайно выудить что-нибудь полезное из скучных творений моего нещадно эксплуатируемого коллеги, Сомс, – возразил я.
– Что, например? – агрессивно вопросил он.
– На меня сильное впечатление произвел такой его аргумент: «Если вы исключите невозможное, то, что останется, каким бы невероятным ни казалось, и будет…
– Ошибкой, – бесцеремонно закончил за меня Сомс. – Если то, что остается, по-настоящему невероятно, значит, вы почти наверняка приняли «по умолчанию» какое-то условие, когда объявляли все другие объяснения невозможными.
Последовательность никогда не значилась в числе добродетелей Сомса.
– Ну, может быть, но…
– Без всяких «но», Ватсап!
– Но ведь в других ситуациях вы соглашались…
– Тьфу! Реальность не бывает невероятной, Ватсап! Она может казаться таковой, но на самом деле ее вероятность составляет 100 %, потому что она уже случилась.
– Ну да, формально это так, но…
– Вот пример. Сегодня утром, когда вы, Ватсап, выходили купить эту лживую газетенку, я принял весьма неожиданного посетителя. Небезызвестного герцога Бамблфортского.
– Главный лондонский щеголь, – сказал я. – Благородный человек безукоризненной честности, образец для всех нас.
– Ну да, ну да. Тем не менее он проинформировал меня… Ну, он рассказал, что в Бамблфорт-холле был обед, на котором эрл Мондеринг, желая развлечь гостей, поставил в ряд десять винных стаканов и наполнил первые пять из них – вот так, – и Сомс продемонстрировал мне этот процесс наглядно, на наших собственных стаканах, наполнив их довольно кислой мадерой, от которой мы как раз решили избавиться. – Затем он предложил гостям переставить стаканы таким образом, чтобы полные чередовались с пустыми.
– Но это очень просто… – начал я.
– Если переставить четыре стакана, то да. Достаточно поменять второй с седьмым и четвертый с девятым. Вот так – (см. рисунок). – Однако эрл просил получить тот же результат, переставив всего два стакана.
Я сложил пальцы перед собой в жесте глубокого размышления и через мгновение нарисовал грубый набросок первоначального и конечного расположения стаканов.
– Но, Сомс! Четыре названных вами стакана должны оказаться в разных местах! Так что без четырех перестановок не обойтись!
Он кивнул.
– Итак, Ватсап, вы только что исключили невозможное.
– Ну да, ей-богу, так я и сделал, Сомс! Неопровержимо.
Он начал набивать табак в свою трубку.
– И к какому же выводу вы придете, если я скажу, что, по словам герцога Бамблфортского, после того как все гости высказались примерно в таком же духе, эрл Мондеринг продемонстрировал верное решение.
– Я… ну…
– Вы вынуждены признать, что благородный герцог, наследник Британской империи и образец высокого благородства… на самом деле низкий лжец. Поскольку никакого решения не существует, как вы только что доказали.
Мое лицо вытянулось.
– Да, правда, все выглядит именно так… Нет, подождите, возможно, это вы не говорите мне…
– Я… ну…
– Вы вынуждены признать, что благородный герцог, наследник Британской империи и образец высокого благородства… на самом деле низкий лжец. Поскольку никакого решения не существует, как вы только что доказали.
Мое лицо вытянулось.
– Да, правда, все выглядит именно так… Нет, подождите, возможно, это вы не говорите мне…
– Мой дорогой доктор, я, честно признаюсь, иногда действительно умалчиваю кое-что, исключительно в ваших интересах, но не в данном случае. Даю слово.
– Но тогда… Я шокирован поведением герцога.
– Оставьте, Ватсап. Имейте веру в британский характер.
– Эрл обманывал?
– Нет-нет-нет. Ничего подобного. Вы способны на большее. В этой ситуации может быть и другое вполне прозаическое объяснение, которое вы проглядели. Более того, могу с уверенностью предсказать, что через несколько минут вы сами будете говорить мне, что решение очень простое и что догадаться может даже ребенок.
После этого Сомс рассказал мне, что сделал Мондеринг.
– Ну, здесь даже ребенок дога… – начал я, но вдруг резко остановился. Должен со всей откровенностью признать, что в этот момент я покраснел как рак.
Какое решение предложил Мондеринг? Ответ см. в главе «Загадки разгаданные».
Сила мидий
Идиллическая сцена на морском берегу: тихая бухта, волны разбиваются о скалы, покрытые водорослями и увешанные гроздьями моллюсков. Кажется, всюду царит сонное спокойствие. На самом деле эти неподвижные скопления мидий – царство непрекращающейся активности; чтобы ее увидеть, нам просто придется ускорить течение времени. При покадровой съемке видно, что моллюски в группах постоянно находятся в движении. Они прикрепляются к камням при помощи особых нитей, которые выделяет нога. Открепляя одни нити и добавляя другие в новых местах, мидия может управлять своим положением на камнях. С одной стороны, мидии любят находиться рядом с себе подобными, потому что вероятность того, что их оторвет от камня волнами, в этом случае заметно меньше. С другой стороны, если рядом нет других мидий, которые составили бы конкуренцию, можно добыть больше пищи. Оказываясь перед такой дилеммой, мидии делают то, что сделало бы на их месте большинство здравомыслящих организмов: идут на компромисс. Они размещаются таким образом, что у каждой мидии оказывается много близких соседей, но мало дальних. То есть они собираются группами. Эти группы – заплатки на дне – видны невооруженным глазом, но вот как они формируются, заметить невозможно.
В 2011 г. Моник де Джагер и ее коллеги применили математику случайного блуждания к моделированию того, как могла сформироваться у мидий групповая стратегия. Случайное блуждание часто сравнивают с движением пьяного по дорожке: то вперед, то назад, без всякой очевидной системы. Если добавить еще одно измерение, получится, что случайное блуждание на плоскости – это серия шагов, длины и направления которых выбираются случайным образом. Разные правила выбора – разные распределения вероятностей для длин и направлений – дают случайные блуждания с разными свойствами. В броуновском движении длины шагов распределяются по колоколовидной кривой вблизи одного конкретного среднего значения шага. В блужданиях Леви[19] вероятность того или иного шага пропорциональна некоторой фиксированной степени его длины, в результате чего многочисленные короткие шаги время от времени прерываются гораздо более длинным шагом.
Статистический анализ наблюдаемых длин шагов ясно показывает, что блуждания Леви вполне соответствуют тому, чем на самом деле занимаются мидии на приливных отмелях, а броуновское движение – нет. Это согласуется и с экологическими моделями, которые математически демонстрируют, что блуждания Леви позволяют мидиям быстрее распространяться, осваивать больше новых площадей и избегать конкуренции с другими видами моллюсков. Это, в свою очередь, позволяет предположить, почему в процессе эволюции появилась именно такая стратегия. Естественный отбор обеспечивает обратную связь между стратегиями передвижения и генетическими инструкциями, предписывающими их применение. У каждой отдельной мидии появляется больше шансов выжить, если она пользуется стратегиями, которые повышают ее шансы на получение пищи и снижают вероятность того, что она будет смыта волнами.
Команда де Джагер использовала данные полевых наблюдений за поведением мидий и математические модели эволюционного процесса. Моделирование показало, что вероятность появления в ходе эволюции блужданий Леви при наличии такой обратной связи достаточно высока, но эволюционно стабильной – то есть не приводящей к катастрофе в случае вторжения какого-либо мутанта с другой стратегией – она становится тогда, когда показатель экспоненты достигает 2. Полевые наблюдения дают величину 2,06.
Устричные поля в этом контексте демонстрируют, что эффективность стратегии движения каждой отдельной мидии зависит от того, что делают все остальные мидии. Стратегия каждой отдельной мидии определяется ее генетикой, но ценность этой стратегии для выживания зависит от коллективного поведения всей местной популяции. Так что здесь мы видим, как окружающая среда – в форме остальных мидий – оказывает влияние на генетический «выбор» индивида и формирует паттерны поведения на уровне популяции.
Дополнительную информацию см. в главе «Загадки разгаданные».
Доказательство шарообразности Земли
Большинство из нас знает, что наша планета по форме круглая – но не точная сфера, а эллипсоид, слегка сплюснутый у полюсов. На ней достаточно неровностей, чтобы при увеличении отклонения от сферической формы примерно в 10 000 раз превратиться в картофелину. Некоторые – их очень немного – упрямцы продолжают настаивать, что Земля плоская, хотя еще древние греки 2500 лет назад собрали достаточно доказательств ее шарообразности, чтобы убедить даже средневековую церковь, а с тех пор доказательств стало намного больше. Вера в то, что Земля плоская, почти полностью ушла, но возродилась примерно в 1883 г. с основанием Зететического общества. Это общество, с 1956 г. известное как Общество плоской Земли, действует и поныне. Вы можете найти его в Интернете, можете следить за событиями в нем в «Фейсбуке» и «Твиттере».
Существует простой и совершенно неопровержимый способ самостоятельно убедиться в том, что наша планета не может быть плоской, если на ней действует обычная геометрия Евклида. Для этого вам потребуется Интернет или общение с терпеливым турагентом – и больше ничего, и речь не идет о том, чтобы посмотреть информацию о форме Земли в Википедии. Описываемая методика не показывает сама по себе, что Земля круглая, но в этом можно убедиться, если ей следовать систематически и аккуратно. Чуть позже мы поговорим о возможных способах отвергнуть полученное доказательство. Я не утверждаю, что таких способов нет: если вы адепт плоской Земли, то способ всегда найдется. Но в данном случае стандартные уловки выглядят еще менее убедительными, чем обычно. Во всяком случае, этот аргумент представляется свежим и необычным на фоне традиционных научных доказательств шарообразности Земли.
Я не имею в виду спутниковые фотографии круглой планеты – они, конечно, подделаны. Все мы знаем, что NASA никогда не летало на Луну, все это снималось в Голливуде, а это доказывает, что и фотографии – фальшивка, так что вот. Не годятся также никакие данные, основанные на научных измерениях: ученые типы – известные шутники, они даже делают вид, что верят в эволюцию и глобальное потепление, а ведь то и другое – это всего лишь левацкие заговоры с целью не дать добропорядочным и во всех отношениях правильным людям зарабатывать неприличные суммы денег, как заповедано Богом.
Нет, я имею в виду исключительно коммерческое доказательство: расписание авиалиний. Их можно легко найти в Интернете: убедитесь только, что вы видите перед собой расписание реальных полетов, а не программы для расчета полетного времени, работающие на основе предположения о шарообразности Земли.
По экономическим причинам все крупные пассажирские самолеты летают примерно на одной скорости. Если бы это было не так, то весь бизнес у медленных компаний перехватили бы их более быстрые конкуренты. По тем же причинам все летают по кратчайшим маршрутам – в той мере, конечно, в какой это допускается местными законами. Поэтому мы можем использовать полетное время как достаточно точную оценку расстояний. (Чтобы снизить влияние ветров, возьмите подходящее среднее значение полетного времени в обоих направлениях – на практике обычного среднего арифметического вполне достаточно.) Затем можно, использовав геодезические методики триангуляции, которые заключаются в построении сети треугольников, нанести на карту расположение нужных аэропортов. Чтобы показать, что плоская модель Земли не годится, мы можем предположить, что планета на самом деле плоская, и посмотреть, что из этого получится. Геодезисты обычно работают с одним-единственным начальным расстоянием – базовой линией, а все остальное рассчитывают через углы треугольников, но у нас есть большое преимущество: мы можем использовать реальные расстояния (в часах полета).