Иэн Стюарт - Математические головоломки профессора Стюарта
- Название:Математические головоломки профессора Стюарта
- Автор:
- Жанр:
- Издательство:Альпина нон-фикшн
- Год:2017
- Город:Москва
- ISBN:978-5-9614-4502-2
- Рейтинг:
- Избранное:Добавить в избранное
-
Отзывы:
-
Ваша оценка:
Иэн Стюарт - Математические головоломки профессора Стюарта краткое содержание
Автор уделяет внимание математическим датам, загадкам простых чисел, теоремам, статистике и множеству других интересных вопросов. Эта умная, веселая книга демонстрирует красоту математики. Из книги читатель узнает о форме апельсиновой кожуры, евклидовых каракулях, блинных числах, о гипотезе квадратного колышка и других решенных и нерешенных задачах. Книга будет интересна всем, кто не равнодушен к загадкам, любит математику и решение головоломок.
Математические головоломки профессора Стюарта - читать онлайн бесплатно ознакомительный отрывок
Интервал:
Закладка:

Как ни удивительно, способ играть в такие карточные игры, как покер, по переписке, по телефону или через Интернет существует, причем без всякой опасности, что кто-то из игроков при этом обманывает. Алиса и Боб могут создать шифр, воспользовавшись теорией чисел, и прибегнуть к сложному обмену посланиями. Такой метод известен как «протокол с нулевым разглашением» – способ убедить собеседника в том, что ты обладаешь каким-то конкретным знанием, не раскрывая, в чем это знание состоит . Так, вы могли бы убедить онлайновую банковскую систему в том, что знаете секретный код, записанный на обороте кредитной карты, не передавая при этом никакой полезной информации о самом коде.
Гостиницы часто хранят ценности гостей в небольших сейфовых ячейках в холле. Для обеспечения безопасности каждая такая ячейка снабжается двумя ключами: один хранится у администратора, другой выдается постояльцу. Чтобы открыть сейф, необходимы оба ключа. Алиса и Боб могут воспользоваться аналогичной схемой:
1. Алиса раскладывает карты по одной в 52 ящичка и запирает их на кодовые замки, ключи к которым известны только ей. Затем она почтой пересылает все ящички Бобу.
2. Боб (который не может отпереть ящички и посмотреть, что за карты в них лежат) выбирает пять ящичков и высылает обратно Алисе. Она отпирает их и получает свои пять карт.
3. Боб выбирает другие пять ящичков и накладывает на каждый из них дополнительный замок. Он знает коды этих замков, Алисе же они неизвестны. Боб высылает эти ящички Алисе.
4. Алиса отпирает свои замки и возвращает ящички Бобу. Теперь он может отпереть их и получить свои пять карт.
После этих предварительных действий может начаться собственно игра. Чтобы раскрыть карты, их пересылают второму игроку. Чтобы доказать, что никто не мошенничал, можно вскрыть все оставшиеся ящички после окончания игры.
Алиса и Боб перевели свою методику игры на язык математики, выделив ее существенные черты. Они представили карточную колоду согласованным набором из 52 чисел. Кодовые замки Алисы обозначаются шифром A , известным только ей. Это функция, математическое правило, превращающее число карты c в другое число Ac . (Я беру на себя вольность не писать всякий раз A ( c ), чтобы не пришлось говорить о «композиции» функций.) Алисе известен также обратный шифр A –1, который переводит Ac обратно в c . То есть
A −1 Ac = c.
Боб не знает ни A , ни A –1.
Аналогично замки Боба соответствуют шифрам B и B –1, известным только ему, таким, что B –1 Bc = c.
С учетом этих предварительных замечаний метод соответствует следующей процедуре:
1. Алиса пересылает все 52 числа Ac 1, …, Ac 52Бобу. Он понятия не имеет, каким картам эти числа соответствуют; по существу, Алиса перетасовала колоду.
2. Боб «сдает» пять карт Алисе и пять самому себе. Он высылает Алисе ее карты. Чтобы упростить запись, рассмотрим лишь одну из этих карт, обозначив ее Ac . Алиса может выяснить значение c , применив к полученному числу A –1, так что она знает, какие карты ей сданы.
3. Бобу необходимо выяснить, какие карты он выбрал для себя, но только Алиса знает, как извлечь истинные значения из зашифрованных. Но Боб не может послать свои карты Алисе, потому что тогда она будет знать, что у него в руке. Поэтому к каждой своей карте Ad он применяет свое шифровальное правило, чтобы получить BAd , и высылает результат такой обработки Алисе.
4. Алиса может вновь применить свое правило A –1, чтобы «снять замок», но на этот раз ее ждет засада: результат будет равен A –1 BAd .
В обычной алгебре мы могли бы поменять A –1и B местами, чтобы получить
BA –1 Ad ,
что равняется Bd .
После этого Алиса могла бы выслать результат обратно Бобу, а тот, в свою очередь, применил бы B –1, чтобы получить d .
Однако функции нельзя переставлять таким образом. К примеру, если Ac = c + 1 (и, соответственно, A –1 c = c – 1) и Bc = c ², то A –1 Bc = Bc – 1 = c ² –1, тогда как
BA –1 c = ( A –1 c )² = ( c – 1)² = c ² –2 c + 1,
то есть совсем не то же самое.
Чтобы обойти это препятствие, следует избегать подобных функций и выбирать такие методы шифрования, для которых A –1 B = BA –1. В этом случае говорят, что для функций A и B действует коммутативный закон , поскольку все это несложно привести к эквивалентному условию AB = BA . Обратите внимание: в описанном нами физическом методе замки Алисы и Боба и правда позволяют перестановку. Их можно навешивать и снимать в любом порядке, результат будет тот же: ящичек с двумя замками.
Таким образом, Алиса и Боб могут играть в покер по переписке, если сумеют придумать два допускающих перестановку шифра A и B , таких, чтобы алгоритм расшифровки A –1 был известен только Алисе, а алгоритм B –1 – только Бобу.
Боб и Алиса выбирают большое простое число p , которое может быть опубликовано и известно всем. Они согласуют также 52 числа c 1, …, c 52(mod p ), которые будут представлять карты.
Алиса выбирает некоторое число a от 1 до p – 2 и определяет свою кодирующую функцию A как Ac = c a (mod p ).
Пользуясь базовой теорией чисел, можно сказать, что обратная (декодирующая) функция имеет вид
A –1 c = c a' (mod p )
для некоего числа a' , которое она может вычислить. Алиса держит и a , и a' в секрете.
Аналогично Боб выбирает себе число b и определяет свою кодирующую функцию B как Bc = c b (mod p ) и обратную к ней
B –1 c = c b' (mod p )
для числа b' , которое он может вычислить. Он держит b и b' в секрете.
Кодирующие функции A и B подчиняются коммуникативному закону, поскольку
ABc = A ( c b ) = ( c b ) a = c ba = c ab = ( c a ) b = B ( c a ) = BAc,
где все равенства выполняются (mod p ). Поэтому Алиса и Боб могут использовать A и B описанным образом.
Исключение невозможного
Из мемуаров доктора Ватсапа
– Ватсап!
– А? Что? Вы это мне, Сомс?
– Сколько раз можно повторять, Ватсап, чтобы вы не приносили журнал The Strand в этот дом!
– Но… как…
– Вы знаете мои методы. Вы нетерпеливо постукивали пальцами, как делаете обычно, пока меня дожидаетесь. При этом вы то и дело поглядывали на свернутую газету, которая торчит у вас из кармана пальто. Газета эта слишком толста для Daily Reporter , хотя именно это название красуется у нее на первой полосе, так что в нее, наверное, завернут какой-то журнал. А поскольку вы по привычке прячете от меня лишь один журнал, сомневаться в его природе не приходится.
Читать дальшеИнтервал:
Закладка: