![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Еще один тест
За несколько тысячелетий кто только не прибегал к услугам математики - от агрономии до физики. Иной раз "под заказ" разрабатывались целые новые направления (матан для обоснования Ньютоновой физики). Но вот недавно мне пришло в голову, что есть практически уникальный пример математического результата, который используется в народном хозяйстве напрямую, не как аппарат для физики и прочих наук. Результат получен в последней четверти 20 века...
Итак, есть три множества A <= B <= C (<= тут обозначает "является подмножеством"). ТЕОРЕМА: A < B (является строгим подмножеством). Эта теорема не доказана (хотя уверенность в ее верности практически всеобщая), в частности, не предъявлен ни один x_i из B-A (однако есть несколько кандидатов на такую роль x_1, x_2,...).
Некоторые из кандидатов x_i используются в бизнесе, оборот которого в мировом масштабе составляет миллиарды, если не триллионы. Относительно некоторых из x_i доказано, что они входят в A, это всякий раз ударяет по названному бизнесу. Опровержение (маловероятное) главной ТЕОРЕМЫ приведет к крушению бизнеса и, возможно, краху всей мировой экономики.
ВНИМАНИЕ, вопрос: что это за множества? О каком бизнесе речь?
Update - Решение задачи
Сначала - краткий ответ для математиков, потом обсуждение для всех. А = P (множество вычислимых функций, для которых существует алгоритм с полиномиальным временем работы), C = Exp (те, для которых существует только экспоненциальный алгоритм), B = NP (множество вычислимых за полиномиальнео время на недетерминированной машине). Хотя то, что P < NP, представляется очевидным, это не доказано и ни один пример функции из NP, для которой доказано, что она не P, не существует.
Далее, если некая обратимая функция из P, то обратная ей, очевидно, из NP. Дадим такое определение.
Пусть существует число k и функция (обратимая) Fk:N -> N такая, что:
a)она легко вычисляется (и алгоритм вычисления не зависит от k);
b)при известном k легко вычисляется обратная к ней (за полином);
c)при неизвестном k обратная вычисляется трудно (принадлежит NP-P).
Такая функция называется односторонней, число k называется секретом.
Легко видеть, что само существование односторонних функций зависит от верности гипотезы P < NP. Тем не менее, есть несколько функций, для которых то, что они именно таковы, кажется очевидным. На основе таких функций и реализующих их алгоритмов создаются системы шифрования с открытым ключом, электронной подписи, распределенного доказательства и т.д. Без этой техники, по-видимому, невозможно функционирование хоть сколько-то защищенных компьютерных сетей. Именно поэтому всякое сообщение о построении очередного алгоритма, более эффективно вычисляющего обратную функцию для известных образцов "односторонней функции", вызывает легкую панику.
Для нематематиков.
До конца 20 века все шифры были симметричными, всякий, кто знал "тайну шифра", мог и писать, и читать шифровку (тайна - какому из "пляшущих человечков" соотвествует какая буква, на каком месте прорези в картонном квадратике, который описан в романе Ж.Верна "Матиас Шандор" и показан в заставке советского фильма "Приключения Шерлока Холмса". В мире таких шифров неразрешима такая, например, задача:
Военный атташе забыл дома шифровальный блокнот. Из посольства он может общаться со своим министром только по прослушиваемой вражеской контрразведкой телеграфной линии. Могут ли министр и атташе обсудить и ввести шифр, который останется неизвестен контрразведке, если они не имеют вначале никакой общей тайной информации (такой, как название книги, которую оба читали в кадетском корпусе, причем они могут намекнуть на нее так, что контрразведка не поймет)? Ответ кажется отрицательным, и казался таковым от Юлия Цезаря до конца 20 века.
Однако вот аналогичная задача: Ульянов-Ленин из Швейцарии едет в пломбированном вагоне в Петроград. Троцкий задумался, как он откроет вагон? Если вагон будет плохо закрыт, агенты Антанты выкрадут вождя. Если переслать дубликат ключа от вагона диппочтой, его также выкрадут, скопируют, вагон откроют. Как быть?
Одно из решений задачи такое: Троцкий изготавливает сейф с захлопывающейся дверцей, оставляет у себя ключ, посылает сейф в Швейцарию. Там в сейф кладут дубликат ключа от вагона, захлопывают дверцу, высылают в Питер. Троцкий открывает сейф своим ключом и получает ключ от вагона, которого нет у Антанты. Можно высылать вагон. (Есть и другое, более простое решение, но это решение иллюстрирует мысль, что существую замки, которые ЛЮБОЙ может закрыть без ключа, но ОТКРЫТЬ может только владелец секретного ключа).
С помощью математического алгоритма, опирающегося на идеи из этой задачи и результаты, описанные выше, в конце 20 века удалось разработать шифры, состоящие из пар "публичный ключ-секретный ключ", причем публичным ключом кто угодно может зашифровать сообщение, но этот ключ не помогает его расшифровать. Это дает решение задачи про атташе (атташе сообщает министру свой публичный ключ, министр высылает атташе забытый блокнот, никто не может прочитать, кроме атташе, у которого секретный ключ, которого не знает ни министр, ни контрразведка). Только такая техника позволяет, например, вводить через интернет пароли доступа к своему счету и т.п., иначе каждый, кто может "слушать" линию между вашим компьютером и сервером, смог бы узнать этот пароль (а технически "слушать" могут все).
А, скажем, электронная подпись - эта же схема, вывернутая наоборот. Вы сообщаете банку открытый ключ, но сообщение банку зашифровываете секретным ключом. Сам факт, что банку удалось расшифровать ваше сообщение, доказывает, что письмо от вас. Даже если (открытый) ключ будет похищен, похитиель не сможет подписать письмо за вас - он только сможет, как и банк, проверить вашу подпись.
Ну а учитывая, какое место в современной экономике занимает банковское дело, а также конфиденциальная связь, понятно, что будет, если вдруго окажутся скомпрометированными все секретные ключи разом - они ведь основаны на НЕДОКАЗАННОЙ теореме, принятой математиками НА ВЕРУ. О как.
За несколько тысячелетий кто только не прибегал к услугам математики - от агрономии до физики. Иной раз "под заказ" разрабатывались целые новые направления (матан для обоснования Ньютоновой физики). Но вот недавно мне пришло в голову, что есть практически уникальный пример математического результата, который используется в народном хозяйстве напрямую, не как аппарат для физики и прочих наук. Результат получен в последней четверти 20 века...
Итак, есть три множества A <= B <= C (<= тут обозначает "является подмножеством"). ТЕОРЕМА: A < B (является строгим подмножеством). Эта теорема не доказана (хотя уверенность в ее верности практически всеобщая), в частности, не предъявлен ни один x_i из B-A (однако есть несколько кандидатов на такую роль x_1, x_2,...).
Некоторые из кандидатов x_i используются в бизнесе, оборот которого в мировом масштабе составляет миллиарды, если не триллионы. Относительно некоторых из x_i доказано, что они входят в A, это всякий раз ударяет по названному бизнесу. Опровержение (маловероятное) главной ТЕОРЕМЫ приведет к крушению бизнеса и, возможно, краху всей мировой экономики.
ВНИМАНИЕ, вопрос: что это за множества? О каком бизнесе речь?
Update - Решение задачи
Сначала - краткий ответ для математиков, потом обсуждение для всех. А = P (множество вычислимых функций, для которых существует алгоритм с полиномиальным временем работы), C = Exp (те, для которых существует только экспоненциальный алгоритм), B = NP (множество вычислимых за полиномиальнео время на недетерминированной машине). Хотя то, что P < NP, представляется очевидным, это не доказано и ни один пример функции из NP, для которой доказано, что она не P, не существует.
Далее, если некая обратимая функция из P, то обратная ей, очевидно, из NP. Дадим такое определение.
Пусть существует число k и функция (обратимая) Fk:N -> N такая, что:
a)она легко вычисляется (и алгоритм вычисления не зависит от k);
b)при известном k легко вычисляется обратная к ней (за полином);
c)при неизвестном k обратная вычисляется трудно (принадлежит NP-P).
Такая функция называется односторонней, число k называется секретом.
Легко видеть, что само существование односторонних функций зависит от верности гипотезы P < NP. Тем не менее, есть несколько функций, для которых то, что они именно таковы, кажется очевидным. На основе таких функций и реализующих их алгоритмов создаются системы шифрования с открытым ключом, электронной подписи, распределенного доказательства и т.д. Без этой техники, по-видимому, невозможно функционирование хоть сколько-то защищенных компьютерных сетей. Именно поэтому всякое сообщение о построении очередного алгоритма, более эффективно вычисляющего обратную функцию для известных образцов "односторонней функции", вызывает легкую панику.
Для нематематиков.
До конца 20 века все шифры были симметричными, всякий, кто знал "тайну шифра", мог и писать, и читать шифровку (тайна - какому из "пляшущих человечков" соотвествует какая буква, на каком месте прорези в картонном квадратике, который описан в романе Ж.Верна "Матиас Шандор" и показан в заставке советского фильма "Приключения Шерлока Холмса". В мире таких шифров неразрешима такая, например, задача:
Военный атташе забыл дома шифровальный блокнот. Из посольства он может общаться со своим министром только по прослушиваемой вражеской контрразведкой телеграфной линии. Могут ли министр и атташе обсудить и ввести шифр, который останется неизвестен контрразведке, если они не имеют вначале никакой общей тайной информации (такой, как название книги, которую оба читали в кадетском корпусе, причем они могут намекнуть на нее так, что контрразведка не поймет)? Ответ кажется отрицательным, и казался таковым от Юлия Цезаря до конца 20 века.
Однако вот аналогичная задача: Ульянов-Ленин из Швейцарии едет в пломбированном вагоне в Петроград. Троцкий задумался, как он откроет вагон? Если вагон будет плохо закрыт, агенты Антанты выкрадут вождя. Если переслать дубликат ключа от вагона диппочтой, его также выкрадут, скопируют, вагон откроют. Как быть?
Одно из решений задачи такое: Троцкий изготавливает сейф с захлопывающейся дверцей, оставляет у себя ключ, посылает сейф в Швейцарию. Там в сейф кладут дубликат ключа от вагона, захлопывают дверцу, высылают в Питер. Троцкий открывает сейф своим ключом и получает ключ от вагона, которого нет у Антанты. Можно высылать вагон. (Есть и другое, более простое решение, но это решение иллюстрирует мысль, что существую замки, которые ЛЮБОЙ может закрыть без ключа, но ОТКРЫТЬ может только владелец секретного ключа).
С помощью математического алгоритма, опирающегося на идеи из этой задачи и результаты, описанные выше, в конце 20 века удалось разработать шифры, состоящие из пар "публичный ключ-секретный ключ", причем публичным ключом кто угодно может зашифровать сообщение, но этот ключ не помогает его расшифровать. Это дает решение задачи про атташе (атташе сообщает министру свой публичный ключ, министр высылает атташе забытый блокнот, никто не может прочитать, кроме атташе, у которого секретный ключ, которого не знает ни министр, ни контрразведка). Только такая техника позволяет, например, вводить через интернет пароли доступа к своему счету и т.п., иначе каждый, кто может "слушать" линию между вашим компьютером и сервером, смог бы узнать этот пароль (а технически "слушать" могут все).
А, скажем, электронная подпись - эта же схема, вывернутая наоборот. Вы сообщаете банку открытый ключ, но сообщение банку зашифровываете секретным ключом. Сам факт, что банку удалось расшифровать ваше сообщение, доказывает, что письмо от вас. Даже если (открытый) ключ будет похищен, похитиель не сможет подписать письмо за вас - он только сможет, как и банк, проверить вашу подпись.
Ну а учитывая, какое место в современной экономике занимает банковское дело, а также конфиденциальная связь, понятно, что будет, если вдруго окажутся скомпрометированными все секретные ключи разом - они ведь основаны на НЕДОКАЗАННОЙ теореме, принятой математиками НА ВЕРУ. О как.